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