Distributed computing of efficient routing schemes in generalized chordal graphs

Abstract : We propose a simple interval routing scheme for a graph $G$, based on a Maximal Neighborhood BFS-tree $T$ of $G$. In our scheme a message simply follows the source-destination path in $T$ but, in at most one step, it may take a shortcut. This shortcut is taken when the current node has a neighbor in $G$ which is an ancestor in $T$ of the destination. In the class of $k$-chordal graphs, this gives an additive stretch of at most $k-1$, and at most $1$ in the class of chordal graphs. Our routing tables use $O(\Delta\log n)$ bits per node, where $\Delta$ is the maximum degree. We propose a simple distributed algorithm to compute such tables in time $O(D)$ in any $n$-node graph with diameter $D$.
Type de document :
Communication dans un congrès
International Colloquium on Structural Information and Communication Complexity (SIROCCO), 2009, Piran, Slovenia. 2009
Liste complète des métadonnées

https://hal.inria.fr/inria-00423454
Contributeur : Nicolas Nisse <>
Soumis le : samedi 10 octobre 2009 - 13:56:44
Dernière modification le : mardi 13 décembre 2016 - 15:44:53

Identifiants

  • HAL Id : inria-00423454, version 1

Collections

Citation

Nicolas Nisse, Ivan Rapaport, Karol Suchan. Distributed computing of efficient routing schemes in generalized chordal graphs. International Colloquium on Structural Information and Communication Complexity (SIROCCO), 2009, Piran, Slovenia. 2009. <inria-00423454>

Partager

Métriques

Consultations de la notice

275