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
Complete list of metadatas

Cited literature [21 references]  Display  Hide  Download

https://hal-lara.archives-ouvertes.fr/hal-02101953
Contributor : Colette Orange <>
Submitted on : Wednesday, April 17, 2019 - 9:10:38 AM
Last modification on : Friday, May 17, 2019 - 1:39:20 AM

File

RR1995-15.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02101953, version 1

Collections

Citation

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⟩

Share

Metrics

Record views

7

Files downloads

31