HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation

Bi-connectivity, k-connectivity and Multipoint Relays

Laurent Viennot 1 Philippe Jacquet 2
1 GANG - Networks, Graphs and Algorithms
LIAFA - Laboratoire d'informatique Algorithmique : Fondements et Applications, Inria Paris-Rocquencourt
2 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 : Multipoint relays were introduced to optimize flooding in ad hoc networks. They are also used to determine a sub-topology containing shortest paths in the OLSR routing protocol. We show that a generalized version of multipoint relays can be used to construct a sub-topology preserving bi-connectivity and more generally $k$-connectivity. Moreover, we show that the multipoint relay structure is intrinsic to any sub-topology with similar properties.
Complete list of metadata

Cited literature [6 references]  Display  Hide  Download

Contributor : Rapport de Recherche Inria Connect in order to contact the contributor
Submitted on : Tuesday, April 24, 2007 - 12:41:15 PM
Last modification on : Friday, January 21, 2022 - 3:15:04 AM
Long-term archiving on: : Tuesday, September 21, 2010 - 12:29:48 PM


Files produced by the author(s)


  • HAL Id : inria-00142851, version 2


Laurent Viennot, Philippe Jacquet. Bi-connectivity, k-connectivity and Multipoint Relays. [Research Report] RR-6169, INRIA. 2007, pp.9. ⟨inria-00142851v2⟩



Record views


Files downloads