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…