Search this article in Google Scholar


分類 国際会議
著者名 (author) Satoshi Fujita
英文著者名 (author)
編者名 (editor)
編者名 (英文)
キー (key)
表題 (title) Worst Case Analysis of a Greedy Multicast Algorithm in k-ary n-cubes
表題 (英文)
書籍・会議録表題 (booktitle) Proc. the 31st International Conference on Parallel Processing (ICPP 2002)
書籍・会議録表題(英文)
巻数 (volume)
号数 (number)
ページ範囲 (pages) 511-518
組織名 (organization) IEEE Computer Society
出版元 (publisher)
出版元 (英文)
出版社住所 (address)
刊行月 (month) August
出版年 (year) 2002
付加情報 (note) Vancouver
注釈 (annote) DOI: 10.1109/ICPP.2002.1040908, Acceptance rate: 68/188 = 36%
内容梗概 (abstract) In this paper, we consider the problem of multicasting a message in k-ary n-cubes under the store-and-forward model. The objective of the problem is to minimize the size of the resultant multicast tree by keeping the distance to each destination over the tree the same as the distance in the original graph. In the following, we first propose an algorithm that grows a multicast tree in a greedy manner, in the sense that for each intermediate vertex of the tree, the outgoing edges of the vertex are selected in a non-increasing order of the number of destinations that can use the edge in a shortest path to the destination. We then evaluate the goodness of the algorithm in terms of the worst case ratio of the size of the generated tree to the size of an optimal tree. It is proved that for any k≥5 and n≥6, the performance ratio of the greedy algorithm is c×kn-o(n) for some constant 1/1.2≤c≤1/2.
論文電子ファイル Not available.


[1-33]  Satoshi Fujita, ``Worst Case Analysis of a Greedy Multicast Algorithm in K-Ary N-Cubes,'' In Proc. the 31st International Conference on Parallel Processing (ICPP 2002), pp. 511-518 , August 2002. (Vancouver)

@inproceedings{1_33,
    author = {Satoshi Fujita},
    author_e = {},
    editor = {},
    editor_e = {},
    title = {Worst Case Analysis of a Greedy Multicast Algorithm in k-ary n-
    cubes},
    title_e = {},
    booktitle = {Proc. the 31st International Conference on Parallel Processing
    (ICPP 2002)},
    booktitle_e = {},
    volume = {},
    number = {},
    pages = {511-518 },
    organization = {IEEE Computer Society},
    publisher = {},
    publisher_e = {},
    address = {},
    month = {August},
    year = {2002},
    note = {Vancouver},
    annote = {DOI: 10.1109/ICPP.2002.1040908, Acceptance rate: 68/188 = 36%}
}

This site is maintained by Distributed System Laboratory.

PMAN 2.5.5 - Paper MANagement system / (C) 2002-2008, Osamu Mizuno / All rights reserved.