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

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 (Research report)
Complete list of metadata
Contributor : Rapport De Recherche Inria Connect in order to contact the contributor
Submitted on : Wednesday, May 24, 2006 - 11:51:29 AM
Last modification on : Friday, October 28, 2022 - 3:28:37 AM
Long-term archiving on: : Sunday, April 4, 2010 - 11:33:59 PM


  • HAL Id : inria-00073097, version 1



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



Record views


Files downloads