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.
Document type :
Reports
Complete list of metadatas

https://hal.inria.fr/inria-00073097
Contributor : Rapport de Recherche Inria <>
Submitted on : Wednesday, May 24, 2006 - 11:51:29 AM
Last modification on : Thursday, February 7, 2019 - 1:49:01 PM
Long-term archiving on : Sunday, April 4, 2010 - 11:33:59 PM

Identifiers

  • 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⟩

Share

Metrics

Record views

301

Files downloads

376