Distributed computing of efficient routing schemes in generalized chordal graphs - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2009

Distributed computing of efficient routing schemes in generalized chordal graphs

Résumé

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$.
Fichier non déposé

Dates et versions

inria-00423454 , version 1 (10-10-2009)

Identifiants

  • HAL Id : inria-00423454 , version 1

Citer

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. ⟨inria-00423454⟩
119 Consultations
0 Téléchargements

Partager

Gmail Facebook X LinkedIn More