Premium
Optimal broadcasting with universal lists based on competitive analysis *
Author(s) -
Kim JaeHoon,
Chwa KyungYong
Publication year - 2005
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.20068
Subject(s) - broadcasting (networking) , hypercube , node (physics) , computer science , scheme (mathematics) , computer network , theoretical computer science , distributed computing , mathematics , parallel computing , mathematical analysis , structural engineering , engineering
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 2005
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom