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 -