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

キー (key) 

表題 (title) 
A Greedy Multicast Algorithm in {kary ncubes} and its Worst Case Analysis 
表題 (英文) 

定期刊行物名 (journal) 
IEICE Trans. on Information and Systems 
定期刊行物名 (英文) 

巻数 (volume) 
E86D 
号数 (number) 
2 
ページ範囲 (pages) 
238245 
刊行月 (month) 
February 
出版年 (year) 
2003 
付加情報 (note) 

注釈 (annote) 

内容梗概 (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 performnance ratio of the greedy algorithm is c×kn  o(n) for some constant 1/12≦c≦1/2. 
論文電子ファイル  Not available. 
 [016] Satoshi Fujita, ``A Greedy Multicast Algorithm in {KAry NCubes} and Its Worst Case Analysis,'' IEICE Trans. on Information and Systems, vol. E86D, no. 2, pp. 238245, February 2003.
@article{0_16, author = {Satoshi Fujita}, author_e = {}, title = {A Greedy Multicast Algorithm in {kary ncubes} and its Worst Case Analysis}, title_e = {}, journal = {IEICE Trans. on Information and Systems}, journal_e = {}, volume = {E86D}, number = {2}, pages = {238245}, month = {February}, year = {2003}, note = {}, annote = {} }
This site is maintained by Distributed System Laboratory. PMAN 2.5.5  Paper MANagement system / (C) 20022008, Osamu Mizuno / All rights reserved. 