7 papers
Sparse Relaxed Broadcast Graphs
Pierre Fraigniaud, Hovhannes Harutyunyan
Broadcasting in graphs refers to the information dissemination problem in which a source node has an atomic piece of information to be distributed to all the nodes of a graph. In t…
Series-Parallel and Planar Graphs for Efficient Broadcasting
David Evangelista, Hovhannes A. Harutyunyan, Aram Khanlari
The broadcasting problem concerns the efficient dissemination of information in graphs. In classical broadcasting, a single originator vertex initially has a message to be transmit…
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…
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…
Source-Oblivious Broadcast
Pierre Fraigniaud, Hovhannes A. Harutyunyan
This paper revisits the study of (minimum) broadcast graphs, i.e., graphs enabling fast information dissemination from every source node to all the other nodes (and having minimum…
Temporal Separators with Deadlines
Hovhannes A. Harutyunyan, Kamran Koupayi, Denis Pankratov
We study temporal analogues of the Unrestricted Vertex Separator problem from the static world. An -temporal separator is a set of vertices whose removal disconnects vertex…