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, Polytechnique - X, 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.
Type de document :
Rapport
[Research Report] RR-6169, INRIA. 2007, pp.9
Liste complète des métadonnées

Littérature citée [6 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00142851
Contributeur : Rapport de Recherche Inria <>
Soumis le : mardi 24 avril 2007 - 12:41:15
Dernière modification le : jeudi 11 janvier 2018 - 06:22:23
Document(s) archivé(s) le : mardi 21 septembre 2010 - 12:29:48

Fichiers

RR-6169.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00142851, version 2

Collections

Citation

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

Partager

Métriques

Consultations de la notice

194

Téléchargements de fichiers

97