ON INTERVAL ROUTING SCHEMES AND TREEWIDTH

In this paper, we investigate which processor networks allow k-label I nterval Routing Schemes, under the assumption that costs of edges may vary. We show that for each fixed k greater than or equal to 1, the cl ass of graphs allowing such routing schemes is closed under minor-taki ng in the domain of connected graphs, and hence has a linear time reco gnition algorithm. This result connects the theory of compact routing with the theory of graph miners and treewidth. We show that every grap h that does not contain K-2,K-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 ar e shown for other types of Interval Routing Schemes. (C) 1997 Academic Press.