zbMATH — the first resource for mathematics

On interval routing schemes and treewidth. (English) Zbl 0892.68069
Summary: 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\geq 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 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.

68R10 Graph theory (including graph drawing) in computer science
Full Text: DOI
[1] Arnborg, S.; Lagergren, J.; Seese, D., Easy problems for tree-decomposable graphs, J. algorithms, 12, 308-340, (1991) · Zbl 0734.68073
[2] Bakker, E.M.; van Leeuwen, J.; Tan, R.B., Linear interval routing schemes, Algorithms rev., 2, 45-61, (1991)
[3] Bienstock, D.; Robertson, N.; Seymour, P.D.; Thomas, R., Quickly excluding a forest, J. combin. theory ser. B, 52, 274-283, (1991) · Zbl 0763.05023
[4] Bodlaender, H.L., A linear time algorithm for finding tree-decompositions of small treewidth, SIAM J. comput., 25, 1305-1317, (1996) · Zbl 0864.68074
[5] Bodlaender, H.L., On linear time minor tests with depth first search, J. algorithms, 14, 1-23, (1993) · Zbl 0764.68107
[6] Bodlaender, H.L., On disjoint cycles, Int. J. found. comput. sci., 5, 59-68, (1994) · Zbl 0803.05030
[7] Bodlaender, Hans L.; van Leeuwen, Jan; Tan, Richard; Thilikos, Dimitrios, Technical report, UU-CS-1996-41, (1996)
[8] Bodlaender, H.L.; Möhring, R.H., The pathwidth and treewidth of cographs, SIAM J. discrete method, 6, 181-188, (1993) · Zbl 0773.05091
[9] Bollobas, B., Random graphs, (1985), Academic Press London · Zbl 0567.05042
[10] Borie, R.B.; Parker, R.G.; Tovey, C.A., Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families, Algorithmica, 7, 555-581, (1992) · Zbl 0753.05062
[11] Cormen, T.H.; Leiserson, C.C.; Rivest, R.L., Introduction to algorithms, (1989), MIT Press Cambridge
[12] Courcelle, B., The monadic second-order logic of graphs. I. recognizable sets of finite graphs, Inform. and comput., 85, 12-75, (1990) · Zbl 0722.03008
[13] Fellows, M.R.; Langston, M.A., Nonconstructive tools for proving polynomial-time decidability, J. assoc. comput. Mach., 35, 727-739, (1988) · Zbl 0652.68049
[14] Fellows, M.R.; Langston, M., On search, decision and the efficiency of polynomial-time algorithms, J. comput. system. sci., 49, 769-779, (1994) · Zbl 0938.68599
[15] Frederickson, G.N.; Janardan, R., Designing networks with compact routing tables, Algorithmica, 3, 171-190, (1988) · Zbl 0646.68087
[16] Inmos, The T9000 transputer products overview manual, (1991)
[17] Kloks, T., Treewidth. computations and approximations, Lecture notes in computer science, 842, (1994), Springer-Verlag Berlin/New York
[18] van Leeuwen, J.; Tan, R.B., Computer networks with compact routing tables, The book ofL, (1986), Springer-Verlag Berlin, p. 298-307 · Zbl 0586.68056
[19] J. van Leeuwen, R. B. Tan, Compact routing methods: A survey, Proceedings, Colloquium on Structural Information and Communication Complexity (SIROCCO’94), 99, 109, School of Computer Science, Carleton University, Ottawa · Zbl 0586.68056
[20] Robertson, N.; Seymour, Graph minors—A survey, (), 153-171
[21] Robertson, N.; Seymour, P.D., Graph minors. V. excluding a planar graph, J. combin. theory ser. B, 41, 92-114, (1986) · Zbl 0598.05055
[22] Robertson, N.; Seymour, P.D., Graph minors. XIII. the disjoint paths problem, J. combin. theory ser. B, 63, 65-110, (1995) · Zbl 0823.05038
[23] Robertson, N.; Seymour, P.D.; Thomas, R., Quickly excluding a planar graph, J. combin. theory ser. B, 62, 323-348, (1994) · Zbl 0807.05023
[24] Santoro, N.; Khatib, R., Labelling and implicit routing in networks, Comput. J., 28, 5-8, (1985) · Zbl 0555.94026
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.