# Distributed computing of efficient routing schemes in generalized chordal graphs

1 MASCOTTE - Algorithms, simulation, combinatorics and optimization for telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
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

https://hal.inria.fr/inria-00423454
Contributeur : Nicolas Nisse <>
Soumis le : samedi 10 octobre 2009 - 13:56:44
Dernière modification le : mercredi 31 janvier 2018 - 10:24:04

### Identifiants

• HAL Id : inria-00423454, version 1

### 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〉

### Métriques

Consultations de la notice