On the complexity of the shortest-path broadcast problem

DOI10.1016/J.DAM.2015.05.004MaRDI QIDQ896659zbMATH OpenOpenAlexFDO

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

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

shortest pathscommunication networksbroadcast timelayered graphs

Mathematics Subject Classification ID

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

Recommendations

• Approximation Algorithms for Minimum-Time Broadcast
• scientific article; zbMATH DE number 1875435
• The complexity of broadcasting in planar and decomposable graphs
• The complexity of broadcasting in planar and decomposable graphs
• Reachability and shortest paths in the broadcast CONGEST model
• On the complexity of equal shortest path routing
• The complexity of rerouting shortest paths
• The complexity of rerouting shortest paths
• Polynomial-time algorithms for minimum-time broadcast in trees
• Optimal broadcast domination in polynomial time

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1875435 (Why is no real title available?)
• scientific article; zbMATH DE number 857072 (Why is no real title available?)
• A Combinatorial Logarithmic Approximation Algorithm for the Directed Telephone Broadcast Problem
• A note on the approximation of the MAX CLIQUE problem
• A polynomial algorithm to compute the minimum degree spanning trees of directed acyclic graphs with applications to the broadcast problem
• A survey of gossiping and broadcasting in communication networks
• An approximation algorithm for the directed telephone multicast problem
• Approximation Algorithms for Minimum-Time Broadcast
• Dissemination of information in communication networks. Broadcasting, gossiping, leader election, and fault-tolerance.
• Information Dissemination in Trees
• Message Multicasting in Heterogeneous Networks
• Methods and problems of communication in usual networks
• Optimization, approximation, and complexity classes
• Simple, fast and deterministic gossip and rumor spreading
• Sublogarithmic approximation for telephone multicast

Cited in

(4)

• scientific article; zbMATH DE number 1875435 (Why is no real title available?)
• The complexity of finding a broadcast center
• The complexity of broadcasting in planar and decomposable graphs
• Efficient approximation algorithms for scheduling moldable tasks

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q896659)