TY - GEN

T1 - On interval routing schemes and treewidth

AU - Bodlaender, Hans L.

AU - Tan, Richard B.

AU - Thilikos, Dimitris M.

AU - Van Leeuwen, Jan

N1 - Publisher Copyright:
© 1995, Springer-Verlag Berlin Heidelberg 1995.

PY - 1995

Y1 - 1995

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84948956679&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84948956679&partnerID=8YFLogxK

U2 - 10.1007/3-540-60618-1_75

DO - 10.1007/3-540-60618-1_75

M3 - Conference contribution

AN - SCOPUS:84948956679

SN - 3540606181

SN - 9783540606185

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 181

EP - 196

BT - Graph-Theoretic Concepts in Computer Science - 21st International Workshop, WG 1995, Proceedings

A2 - Nagl, Manfred

PB - Springer Verlag

T2 - 21st International Workshop on Graph-Theoretic Concepts in Computer Science, WG 1995

Y2 - 20 June 1995 through 22 June 1995

ER -