Improved upper and lower bounds for k-broadcasting
We continue the investigation of k-broadcasting, a variant of broadcasting in which an informed vertex can call up to k of its neighbors in each time unit. A focus of the investigation into broadcasting is the function B-k(n), which is the minimum number of edges in any n vertex graph such that each vertex can originate a k-broadcast that completes in minimum time. We give several methods to construct graphs which allow minimum-time k-broadcasting from each vertex. These constructions give improvements to the best current upper bounds on B-k(n). We also give an improvement to the best existing lower bound on Bk(n). In addition, a few new exact values of B-k(n) are determined. (C) 2001 John Wiley & Sons, Inc.
k-broadcast broadcast minimum broadcast graphs