A Linear-Time Optimal Broadcasting Algorithm in Stars of Cliques

Abstract

For the telephone broadcast model, an $O(n\log n)$-time algorithm for constructing an optimal broadcasting scheme in a star of cliques with a total of $n$ vertices was recently presented by Ambashankar and Harutyunyan at IWOCA 2024. In the present note we give a considerably shorter and purified algorithm description and correctness proof. Moreover, we improve the time complexity to $O(n)$.