Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
420409 | Discrete Applied Mathematics | 2009 | 6 Pages |
We begin an investigation of broadcasting from multiple originators, a variant of broadcasting in which any kk vertices may be the originators of a message in a network of nn vertices. The requirement is that the message be distributed to all nn vertices in minimum time. A minimum kk-originator broadcast graph is a graph on nn vertices with the fewest edges such that any subset of kk vertices can broadcast in minimum time. Bk(n)Bk(n) is the number of edges in such a graph. In this paper, we present asymptotic upper and lower bounds on Bk(n)Bk(n). We also present an exact result for the case when k≥n2. 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.