Broadcasting in Stars of Cliques

Broadcasting is an information dissemination problem in a connected network. One informed node, called the originator, must distribute a message to all other nodes by placing a series of calls along the communication lines of the network. Once a node has been informed, it contributes to the broadcasting process by distributing the message to its neighbors. Finding the broadcast time of any node in an arbitrary network is NP-complete. Polynomial time algorithms have been identified for specific topologies, while heuristics and approximation algorithms have been discovered for some others, but the problem remains open for many topologies. In this paper, we study the broadcasting problem in a topology that can be represented by the Windmill graph \(Wd_{k,l}\) , which contains k cliques of size l, connected to a universal node. We also investigate the broadcast problem in Star of Cliques, which is an extension of the Windmill graph with arbitrary clique sizes. We present an algorithm to find the broadcast time of any node in an arbitrary star of cliques and prove the optimality of the algorithm.