Bi-connexité, k-connexité et multipoints relais

Laurent Viennot (1) , Philippe Jacquet (2)

1 GANG - Networks, Graphs and Algorithms
2 HIPERCOM - High performance communication

Les multipoints relais ont été introduits pour optimiser l'inondation dans un réseau ad hoc. Ils servent aussi, dans le protocole OLSR, à déterminer une sous-topologie qui conserve les plus courts chemin. Nous montrons, comment une généralisation des multipoints relais permet d'obtenir une sous-topologie conservant des propriétés de bi-connexité et plus généralement de k-connexité. Nous montrons de plus, que cette structure de multipoints relais est intrinsèque à toute sous-topologie montrant les mêmes propriétés.

Domaines: Algorithme et structure de données [cs.DS]; Réseaux et télécommunications [cs.NI]

Laurent Viennot, Philippe Jacquet. Bi-connexité, k-connexité et multipoints relais. 9ème Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications, May 2007, Ile d'Oléron, France. pp.9-12. ⟨inria-00176939⟩