On the complexity of the shortest-path broadcast problem

DOI10.1016/j.dam.2015.05.004zbMath1326.05040OpenAlexW786724073MaRDI QIDQ896659

Magnús M. Halldórsson, Geppino Pucci, Chiara Pierucci, Pierluigi Crescenzi, Hovhannes A. Harutyunyan, Pierre Fraigniaud, Andrea Pietracaprina

Publication date: 10 December 2015

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2015.05.004

zbMATH Keywords

communication networksshortest pathsbroadcast timelayered graphs

Mathematics Subject Classification ID

Small world graphs, complex networks (graph-theoretic aspects) (05C82) Paths and cycles (05C38) Distance in graphs (05C12) Directed graphs (digraphs), tournaments (05C20)

Related Items (1)

Efficient approximation algorithms for scheduling moldable tasks

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A polynomial algorithm to compute the minimum degree spanning trees of directed acyclic graphs with applications to the broadcast problem
• A note on the approximation of the MAX CLIQUE problem
• Optimization, approximation, and complexity classes
• Methods and problems of communication in usual networks
• Dissemination of information in communication networks. Broadcasting, gossiping, leader election, and fault-tolerance.
• Sublogarithmic approximation for telephone multicast
• An approximation algorithm for the directed telephone multicast problem
• Simple, Fast and Deterministic Gossip and Rumor Spreading
• A survey of gossiping and broadcasting in communication networks
• Information Dissemination in Trees
• Message Multicasting in Heterogeneous Networks
• Approximation Algorithms for Minimum-Time Broadcast
• A Combinatorial Logarithmic Approximation Algorithm for the Directed Telephone Broadcast Problem

This page was built for publication: On the complexity of the shortest-path broadcast problem