Complexity Results on Election of Multipoint Relays in Wireless Networks

Laurent Viennot 1
1 HIPERCOM - High performance communication
Inria Paris-Rocquencourt, UP11 - Université Paris-Sud - Paris 11, Inria Saclay - Ile de France, X - École polytechnique, CNRS - Centre National de la Recherche Scientifique : UMR
Abstract : The election of multipoint relays allows to decrease the cost of broadcasting in wireless networks. For each source, the fewer elements the set has, the greater the gain is. In this paper, we prove that the computation of a multipoint relay set with minimal size is NP-complete. We also make the analysis of a heuristic proposed by A. Qayyum.
Type de document :
Rapport
[Research Report] RR-3584, INRIA. 1998
Liste complète des métadonnées

https://hal.inria.fr/inria-00073097
Contributeur : Rapport de Recherche Inria <>
Soumis le : mercredi 24 mai 2006 - 11:51:29
Dernière modification le : vendredi 25 mai 2018 - 12:02:06
Document(s) archivé(s) le : dimanche 4 avril 2010 - 23:33:59

Fichiers

Identifiants

  • HAL Id : inria-00073097, version 1

Collections

Citation

Laurent Viennot. Complexity Results on Election of Multipoint Relays in Wireless Networks. [Research Report] RR-3584, INRIA. 1998. 〈inria-00073097〉

Partager

Métriques

Consultations de la notice

279

Téléchargements de fichiers

338