2 papers
cs.DS2026
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…
cs.DS2026
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…