Bounded-Call Broadcasting
Arthur Farley, Andrzej Proskurowski
Committee:
Technical Report(Aug 1991)
Keywords:

Broadcasting is the information dissemination task whereby a message from one site of a network (the sender) is transmitted to all other sites (receivers). In this paper, we initiate the study of broadcasting under operational protocols that bound the number of calls made by any site to be less than or equal to a predetermined constant, c. Specifically, we: (i) investigate the c-call broadcast time function, being the minimum possible time required to inform all vertices in a network when the number of calls made by each site is bounded by c; (ii) define a general class of sparse minimum time c-call broadcast graphs and an associated broadcast protocol; (iii) characterize the structure of minimum broadcast trees with call bound c; (iv) discuss the com­plexity of the recognition problem for minimum time c-call broadcast graphs, and (v) present a catalog of minimum 2-call broadcast graphs, for small values of n.