Approximation Algorithms for Minimum-Time Broadcast
Guy Kortsarz, David Peleg · SIAM Journal on Discrete Mathematics · 1995
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 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.