1999 International Symposium on Parallel Architectures, Algorithms and Networks (ISPAN '99)
On the Interval Routing of Chordal Rings
Fremantle, Australia
June 23-June 25
ISBN: 0-7695-0231-8
The Shortest-Path Interval Routing Scheme is an efficient strategy to code distributed routing algorithms in a compact way. Characterising networks which admit shortest-path Strict Interval Routing Scheme using one interval per edge (1-SIRS) is known to be NP-complete. In this paper, we study 1-SIRS for a popular class of networks, known as Chordal Rings.We prove that for any chordal ring of degree 4 with a chord of length k (>3), there exists an infinite set of n such that the chordal ring <1,k>_n (of size n) does not admit a 1-SIRS, regardless of the node-labeling. This gives a negative answer to an open-question from Gavoille and extends the characterisation of node-labelings which allow a shortest path 1-SIRS in chordal rings.Mainly, we study the natural cyclic node-labeling and derive an alternative node-labeling using isomorphic properties. First we show that there is an infinite class of chordal rings with chord k of even length that do not have a shortest-path 1-SIRS. Second, we show the limitation of the cyclic node-labeling and its alternative representation when k is odd. Finally, we conjecture that any chordal ring with shortest path 1-SIRS has a node-labeling isomorphic to a chordal ring with a cyclic node-labeling.
Index Terms:
Circulant Graph, Chordal Ring, Interval Routing Scheme, Graph Isomorphism, Shortest Path
Citation:
Bernard Mans, "On the Interval Routing of Chordal Rings," ispan, pp.16, 1999 International Symposium on Parallel Architectures, Algorithms and Networks (ISPAN '99), 1999