On Interval Routing Schemes and Treewidth

Hans L. Bodlaender, Jan Van Leeuwen, Richard Tan, Dimitrios M. Thilikos

Research output: Contribution to journalArticlepeer-review


In this paper, we investigate which processor networks allow k-label Interval Routing Schemes, under the assumption that costs of edges may vary. We show that for each fixed k ≥ 1, the class of graphs allowing such routing schemes is closed under minor-taking in the domain of connected graphs, and hence has a linear time recognition algorithm. This result connects the theory of compact routing with the theory of graph minors and treewidth. We show that every graph that does not contain K2, r as a minor has treewidth at most 2r - 2. As a consequence, graphs that allow k-label Interval Routing Schemes under dynamic cost edges have treewidth at most 4k. Similar results are shown for other types of Interval Routing Schemes.

Original languageEnglish (US)
Pages (from-to)92-109
Number of pages18
JournalInformation and Computation
Issue number1
StatePublished - Nov 25 1997

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Information Systems
  • Computer Science Applications
  • Computational Theory and Mathematics


Dive into the research topics of 'On Interval Routing Schemes and Treewidth'. Together they form a unique fingerprint.

Cite this