2 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
A Linear-Time 1.5-Approximation for Broadcasting in k-Cycle Graphs
Jeffrey Bringolf, Anne-Laure Ehresmann, Hovhannes A. Harutyunyan
Broadcasting is an information dissemination primitive where a message originates at a node (called the originator) and is passed to all other nodes in the network. Broadcasting re…