業績データ詳細表示 
 Search this article in Google Scholar
分類  国際会議 
著者名 (author) 
Satoshi Fujita 
英文著者名 (author) 

編者名 (editor) 

編者名 (英文) 

キー (key) 

表題 (title) 
Worst Case Analysis of a Greedy Multicast Algorithm in kary ncubes 
表題 (英文) 

書籍・会議録表題 (booktitle) 
Proc. the 31st International Conference on Parallel Processing (ICPP 2002) 
書籍・会議録表題(英文) 

巻数 (volume) 

号数 (number) 

ページ範囲 (pages) 
511518 
組織名 (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 kary ncubes under the storeandforward 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 nonincreasing 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×kno(n) for some constant 1/1.2≤c≤1/2. 
論文電子ファイル  Not available. 
 [133] Satoshi Fujita, ``Worst Case Analysis of a Greedy Multicast Algorithm in KAry NCubes,'' In Proc. the 31st International Conference on Parallel Processing (ICPP 2002), pp. 511518 , August 2002. (Vancouver)
@inproceedings{1_33, author = {Satoshi Fujita}, author_e = {}, editor = {}, editor_e = {}, title = {Worst Case Analysis of a Greedy Multicast Algorithm in kary n cubes}, title_e = {}, booktitle = {Proc. the 31st International Conference on Parallel Processing (ICPP 2002)}, booktitle_e = {}, volume = {}, number = {}, pages = {511518 }, 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) 20022008, Osamu Mizuno / All rights reserved. 