Approximation Algorithms for Minimum-Time Broadcast

This paper deals with the problem of broadcasting in minimum time in the telephone and message-passing models. Approximation algorithms are developed for arbitrary graphs as well as for several restricted graph classes. In particular, an $O(\sqrt{n})$-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 model) 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.