Skip to Main content Skip to Navigation
Conference papers

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$.
Document type :
Conference papers
Complete list of metadata

https://hal.inria.fr/inria-00423454
Contributor : Nicolas Nisse <>
Submitted on : Saturday, October 10, 2009 - 1:56:44 PM
Last modification on : Monday, October 12, 2020 - 10:30:12 AM

Identifiers

  • 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. ⟨inria-00423454⟩

Share

Metrics

Record views

430