Optimal broadcasting with universal lists based on competitive analysis
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. (c) 2005 Wiley Periodicals, Inc.
broadcasting competitive analysis tree grid complete graph hypercube