## Abstract

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.

Original language | English |
---|---|

Pages (from-to) | 16-21 |

Number of pages | 6 |

Journal | Proceedings of the International Symposium on Parallel Architectures, Algorithms and Networks, I-SPAN |

Publication status | Published - 1999 |