On the Complexity of Telephone Broadcasting: From Cacti to Bounded Pathwidth Graphs

Aida Aminian, Shahin Kamali, Seyed-Mohammad Seyed-Javadi +1

In the Telephone Broadcasting problem, the goal is to disseminate a message from a given source vertex of an input graph to all other vertices in the minimum number of rounds, wher…