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