HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
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

Contributor : Nicolas Nisse Connect in order to contact the contributor
Submitted on : Saturday, October 10, 2009 - 1:56:44 PM
Last modification on : Friday, February 4, 2022 - 3:18:04 AM


  • HAL Id : inria-00423454, version 1


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⟩



Record views