D.: Approximation algorithms for minimum-time broadcast

Abstract. This paper deals with the problem of broadcasting in minimum time in the tele-phone and message-passing models. Approximation algorithms are developed for arbitrary graphs as well as for several restricted graph classes. In particular, an O(vfvT)-additive approximation algorithm is given for broadcasting in general graphs, and an O(log n / log log n) (multiplicative) ratio approximation is given for broadcasting in the open-path model. This also results in an algorithm for broadcasting on random graphs (in the telephone and message-passing models) that yields an O(log n / log log n) approximation with high probability. In addition, the paper presents a broadcast algorithm for graph families with small separators (such as chordal, k-outerplanar, bounded-face planar, and series-parallel graphs), with approximation ratio proportional to the separator size times log n. Finally, an efficient approximation algorithm is presented for the class of graphs representable as trees of cliques. Key words, broadcast, approximation AMS subject classifications. 05C85, 68Q25, 90C27, 90B3