On interval routing schemes and treewidth

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

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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 also show that every graph that does not contain K2,r as a minor has treewidth at most 2r – 2. In case the graph is planar, this bound can be lowered to r + 2. As a consequence, graphs that allow k-label Interval Routing Schemes under dynamic cost edges have treewidth at most 4k, and treewidth at most 2k + 3 if they are planar. Similar results are shown for other types of Interval Routing Schemes.

Original languageEnglish (US)
Title of host publicationGraph-Theoretic Concepts in Computer Science - 21st International Workshop, WG 1995, Proceedings
EditorsManfred Nagl
PublisherSpringer Verlag
Number of pages16
ISBN (Print)3540606181, 9783540606185
StatePublished - 1995
Event21st International Workshop on Graph-Theoretic Concepts in Computer Science, WG 1995 - Aachen, Germany
Duration: Jun 20 1995Jun 22 1995

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference21st International Workshop on Graph-Theoretic Concepts in Computer Science, WG 1995

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'On interval routing schemes and treewidth'. Together they form a unique fingerprint.

Cite this