Abstract | ||
---|---|---|
In this article we study a variant of broadcasting: each node has a predetermined ordered list of neighbors regardless of the node, called the source, from which the originating message is transmitted to all nodes in a network. Each node transmits a received message to its neighbors in order of the list. We propose a new measure of the efficiency of a Broadcasting scheme, which is obtained from competitive analysis, and we design new broadcasting schemes for lines, complete k-ary trees, grids, complete graphs, and hypercubes. In particular, we provide optimal broadcasting schemes for lines and grids. © 2005 Wiley Periodicals, Inc. NETWORKS, Vol. 45(4), 224–231 2005A preliminary version of this article appeared in the Proceedings of the 12th ISAAC Conference, Lecture Notes in Computer Science, vol. 2223, 74-85, 2001. |
Year | DOI | Venue |
---|---|---|
2005 | 10.1002/net.v45:4 | Networks |
Keywords | Field | DocType |
hypercube,grid,complete graph,tree,competitive analysis,broadcasting | Broadcasting,Graph,Complete graph,Combinatorics,Computer science,Computer network,Theoretical computer science,Online analytical processing,Grid,Hypercube,Competitive analysis | Journal |
Volume | Issue | ISSN |
45 | 4 | 0028-3045 |
Citations | PageRank | References |
3 | 0.49 | 3 |
Authors | ||
2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Jae-Hoon Kim | 1 | 268 | 65.73 |
Kyung-Yong Chwa | 2 | 919 | 97.10 |