3 papers
cs.DS2025
On Hardness and Approximation of Broadcasting in Structured Graphs
Jeffrey Bringolf, Hovhannes A. Harutyunyan, Shahin Kamali +1
We study the Telephone Broadcasting problem in graphs with restricted structure. Given a designated source in an undirected graph, the goal is to disseminate a message to all verti…
cs.DS2025
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…
cs.GT2022
Rainbow Cycle Number and EFX Allocations: (Almost) Closing the Gap
Shayan Chashm Jahan, Masoud Seddighin, Seyed-Mohammad Seyed-Javadi +1
Recently, some studies on the fair allocation of indivisible goods notice a connection between a purely combinatorial problem called the Rainbow Cycle problem and a fairness notion…