On the interval routing of chordal rings

Bernard Mans*

*Corresponding author for this work

Research output: Contribution to journalArticle

4 Citations (Scopus)

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 languageEnglish
Pages (from-to)16-21
Number of pages6
JournalProceedings of the International Symposium on Parallel Architectures, Algorithms and Networks, I-SPAN
Publication statusPublished - 1999

Fingerprint Dive into the research topics of 'On the interval routing of chordal rings'. Together they form a unique fingerprint.

  • Cite this