Improved upper and lower bounds fork-broadcasting
Hovhannes A. Harutyunyan, Arthur L. Liestman · Networks · 2001
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 Bk(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 Bk(n). We also give an improvement to the best existing lower bound on Bk(n). In addition, a few new exact values of Bk(n) are determined. © 2001 John Wiley & Sons, Inc.