Abstract
In this paper, we propose two one-to-all optimal broadcasting algorithms in incomplete star graphs. An incomplete star graph with N nodes, where (n - l)! < N < n!, is a subgraph of an n-star. Using a routing scheme to transmit a message to each substar composed of the incomplete star, our proposed broadcasting algorithm is optimal in O(n1ogn) on the single-port communication model. While broadcasting m messages on the incomplete star, we also present an optimal algorithm in O(n log n+m). Multi-message broadcasting as done first by transmitting m messages to each substar in a pipelined fashion and then by using the algorithm in [I21 to broadcast them.