Optimal Broadcasting Algorithm for Multiple Messages on the Star and Pancake Graphs Using Minimum Dominating Sets

摘要

We present broadcasting algorithms for the n-star and n-pancake graphs for m messages. Both the n-star and n-pancake have n! vertices but with sub-logarithmic degrees and diameters in terms of the total number of vertices. The algorithms use minimum dominating sets and run in O(m + n) time, which is optimal.