# NSR12

### Summary

**Nicolas Nisse, Ivan Rapaport and Karol Suchan** (2012) *Distributed computing of efficient routing schemes in generalized chordal graphs.* Theoretical Compututer Science, 444:17-27. (PDF)

### 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$}.

### Bibtex entry

`@ARTICLE { NSR12,`

AUTHOR = { Nicolas Nisse and Ivan Rapaport and Karol Suchan },

TITLE = { Distributed computing of efficient routing schemes in generalized chordal graphs },

JOURNAL = { Theoretical Compututer Science },

VOLUME = { 444 },

YEAR = { 2012 },

MONTH = { jul },

PAGES = { 17-27 },

PDF = { http://www-sop.inria.fr/members/Nicolas.Nisse/publications/distribRouting.pdf },

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$}. },

}