On the complexity of the shortest-path broadcast problem

Abstract : We study the shortest-path broadcast problem in graphs and digraphs, where a message has to be transmitted from a source node s to all the nodes along shortest paths, in the classical telephone model. For both graphs and digraphs, we show that the problem is equivalent to the broadcast problem in layered directed graphs. We then prove that this latter problem is NP-hard, and therefore that the shortest-path broadcast problem is NP-hard in graphs as well as in digraphs. Nevertheless, we prove that a simple polynomial-time algorithm, called MDST-broadcast, based on min-degree spanning trees, approximates the optimal broadcast time within a multiplicative factor 3/2 in 3-layer digraphs, and O(log n/loglog n) in arbitrary multi-layer digraphs. As a consequence, one can approximate the optimal shortest-path broadcast time in polynomial time within a multiplicative factor 3/2 whenever the source has eccentricity at most 2, and within a multiplicative factor O(log n/\log\log n) in the general case, for both graphs and digraphs. The analysis of MDST-broadcast is tight, as we prove that this algorithm cannot approximate the optimal broadcast time within a factor smaller than Omega(log n/log\log n).
Type de document :
Article dans une revue
Discrete Applied Mathematics, Elsevier, 2016, 199, pp.101-109. 〈10.1016/j.dam.2015.05.004〉
Liste complète des métadonnées

Littérature citée [21 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01255198
Contributeur : Pierre Fraigniaud <>
Soumis le : mercredi 13 janvier 2016 - 11:55:46
Dernière modification le : jeudi 14 juin 2018 - 10:54:02
Document(s) archivé(s) le : vendredi 11 novembre 2016 - 04:47:27

Fichier

broadcast.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Pierluigi Crescenzi, Pierre Fraigniaud, Magnus M. Halldorsson, Hovhannes Harutyunyan, Chiara Pierucci, et al.. On the complexity of the shortest-path broadcast problem. Discrete Applied Mathematics, Elsevier, 2016, 199, pp.101-109. 〈10.1016/j.dam.2015.05.004〉. 〈hal-01255198〉

Partager

Métriques

Consultations de la notice

273

Téléchargements de fichiers

148