Search this article in Google Scholar


分類 論文誌
著者名 (author) Satoshi Fujita
英文著者名 (author)
キー (key)
表題 (title) A Greedy Multicast Algorithm in {k-ary n-cubes} and its Worst Case Analysis
表題 (英文)
定期刊行物名 (journal) IEICE Trans. on Information and Systems
定期刊行物名 (英文)
巻数 (volume) E86-D
号数 (number) 2
ページ範囲 (pages) 238-245
刊行月 (month) February
出版年 (year) 2003
付加情報 (note)
注釈 (annote)
内容梗概 (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 performnance ratio of the greedy algorithm is c×kn - o(n) for some constant 1/12≦c≦1/2.
論文電子ファイル Not available.


[0-16]  Satoshi Fujita, ``A Greedy Multicast Algorithm in {K-Ary N-Cubes} and Its Worst Case Analysis,'' IEICE Trans. on Information and Systems, vol. E86-D, no. 2, pp. 238-245, February 2003.

@article{0_16,
    author = {Satoshi Fujita},
    author_e = {},
    title = {A Greedy Multicast Algorithm in {k-ary n-cubes} and its Worst Case
    Analysis},
    title_e = {},
    journal = {IEICE Trans. on Information and Systems},
    journal_e = {},
    volume = {E86-D},
    number = {2},
    pages = {238-245},
    month = {February},
    year = {2003},
    note = {},
    annote = {}
}

This site is maintained by Distributed System Laboratory.

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