Broadcasting from multiple originators |
| |
Authors: | Arthur L Liestman Dana Richards |
| |
Institution: | a School of Computing Science, Simon Fraser University, Burnaby, BC V5A 1S6, Canada b Department of Computer Science, George Mason University, MSN 4A5, 4400 University Drive, Fairfax, VA 22030, USA c Department of Mathematics, Simon Fraser University, Burnaby, BC V5A 1S6, Canada |
| |
Abstract: | We begin an investigation of broadcasting from multiple originators, a variant of broadcasting in which any k vertices may be the originators of a message in a network of n vertices. The requirement is that the message be distributed to all n vertices in minimum time. A minimumk-originator broadcast graph is a graph on n vertices with the fewest edges such that any subset of k vertices can broadcast in minimum time. Bk(n) is the number of edges in such a graph. In this paper, we present asymptotic upper and lower bounds on Bk(n). We also present an exact result for the case when . We also give an upper bound on the number of edges in a relaxed version of this problem in which one additional time unit is allowed for the broadcast. |
| |
Keywords: | Broadcast Multiple originator Minimum broadcast graph Relaxed broadcast |
本文献已被 ScienceDirect 等数据库收录! |
|