Skip to Main content Skip to Navigation
New interface
Reports (Research report)

Approximation algorithms for information dissemination problems.

Abstract : Broadcasting and gossiping are known to be NP-hard problems. This paper deals with approximation algorithms for such problems. We consider both round-complexity and step-complexity in the telephone model. After an overview of previously derived approximation algorithms, we present new strategies for broadcasting and gossiping in any graphs. Broadcasting strategies are based on the construction of edge-disjoint spanning trees. Gossiping strategies are based on on-line computation of matchings along with the gossiping process. Our approximation algorithms for broadcasting offer almost optimal complexity when the number of messages to be broadcasted is large. We show that our best approximation algorithm for gossiping performs optimally in many cases. We also show experimentally that it can perform faster than the best known handmade algorithms in some particular cases.
Document type :
Reports (Research report)
Complete list of metadata

Cited literature [41 references]  Display  Hide  Download
Contributor : Colette ORANGE Connect in order to contact the contributor
Submitted on : Wednesday, April 17, 2019 - 9:10:38 AM
Last modification on : Wednesday, October 26, 2022 - 8:15:02 AM


Files produced by the author(s)


  • HAL Id : hal-02101953, version 1



Pierre Fraigniaud, Sandrine Vial. Approximation algorithms for information dissemination problems.. [Research Report] LIP RR-1995-15, Laboratoire de l'informatique du parallélisme. 1995, 2+23p. ⟨hal-02101953⟩



Record views


Files downloads