Skip to main content
SpringerLink
Log in

Treewidth: Algorithmic techniques and results

  • Invited Papers
  • Conference paper
  • First Online:
Mathematical Foundations of Computer Science 1997 (MFCS 1997)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 1295))

Abstract

This paper gives an overview of several results and techniques for graphs algorithms that compute the treewidth of a graph or that solve otherwise intractable problems when restricted graphs with bounded treewidth more efficiently. Also, several results on graph minors are reviewed.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

References

  1. K. A. Abrahamson, R. G. Downey, and M. R. Fellows. Fixed-parameter tractability and completeness IV: On completeness for W[P] and PSPACE analogues. Annals of Pure and Applied Logic, 73:235–276, 1995.

    Article  Google Scholar 

  2. K. R. Abrahamson and M. R. Fellows. Finite automata, bounded treewidth and well-quasiordering. In N. Robertson and P. Seymour, editors, Proceedings of the AMS Summer Workshop on Graph Minors, Graph Structure Theory, Contemporary Mathematics vol. 147, pages 539–564. American Mathematical Society, 1993.

    Google Scholar 

  3. S. Arnborg. Some PSPACE-complete logic decision problems that become linear time solvable on formula graphs of bounded treewidth. Manuscript, 1991.

    Google Scholar 

  4. S. Arnborg. Graph decompositions and tree automata in reasoning with uncertainty. J. Expt. Theor. Artif. Intell., 5:335–357, 1993.

    Google Scholar 

  5. S. Arnborg, D. G. Corneil, and A. Proskurowski. Complexity of finding embeddings in a k-tree. SIAM J. Alg. Disc. Meth., 8:277–284, 1987.

    Google Scholar 

  6. S. Arnborg, B. Courcelle, A. Proskurowski, and D. Seese. An algebraic theory of graph reduction. J. ACM, 40:1134–1164, 1993.

    Article  Google Scholar 

  7. S. Arnborg, J. Lagergren, and D. Seese. Easy problems for tree-decomposable graphs. J. Algorithms, 12:308–340, 1991.

    Article  Google Scholar 

  8. S. Arnborg and A. Proskurowski. Characterization and recognition of partial 3-trees. SIAM J. Alg. Disc. Meth., 7:305–314, 1986.

    Google Scholar 

  9. S. Arnborg and A. Proskurowski. Linear time algorithms for NP-hard problems restricted to partial k-trees. Disc. Appl. Math., 23:11–24, 1989.

    Article  Google Scholar 

  10. S. Arnborg and A. Proskurowski. Canonical representations of partial 2-and 3-trees. BIT, 32:197–214, 1992.

    Article  Google Scholar 

  11. S. Arnborg, A. Proskurowski, and D. G. Corneil. Forbidden minors characterization of partial 3-trees. Disc. Math., 80:1–19, 1990.

    Article  Google Scholar 

  12. S. Arnborg, A. Proskurowski, and D. Seese. Monadic second order logic, tree automata and forbidden minors. In E. Börger, H. Kleine Büning, M. M. Richter, and W. Schönfeld, editors, Proceedings 4th Workshop on Computer Science Logic, CSL'90, pages 1–16. Springer Verlag, LNCS, vol. 533, 1991.

    Google Scholar 

  13. M. W. Bern, E. L. Lawler, and A. L. Wong. Linear time computation of optimal subgraphs of decomposable graphs. J. Algorithms, 8:216–235, 1987.

    Article  Google Scholar 

  14. D. Bienstock. Graph searching, path-width, tree-width and related problems (a survey). DIMACS Ser. in Discrete Mathematics and Theoretical Computer Science, 5:33–49, 1991.

    Google Scholar 

  15. D. Bienstock and M. A. Langston. Algorithmic implications of the graph minor theorem. To appear as chapter in: Handbook of Operations Research and Management Science: Volume on Networks and Distribution, 1993.

    Google Scholar 

  16. D. Bienstock, N. Robertson, P. D. Seymour, and R. Thomas. Quickly excluding a forest. J. Comb. Theory Series B, 52:274–283, 1991.

    Article  Google Scholar 

  17. H. L. Bodlaender. NC-algorithms for graphs with small treewidth. In J. van Leeuwen, editor, Proceedings 14th International Workshop on Graph-Theoretic Concepts in Computer Science WG'88, pages 1–10. Springer Verlag, LNCS, vol. 344, 1988.

    Google Scholar 

  18. H. L. Bodlaender. Polynomial algorithms for graph isomorphism and chromatic index on partial k-trees. J. Algorithms, 11:631–643, 1990.

    Article  Google Scholar 

  19. H. L. Bodlaender. Complexity of path-forming games. Theor. Comp. Sc., 110:215–245, 1993.

    Article  Google Scholar 

  20. H. L. Bodlaender. On linear time minor tests with depth first search. J. Algorithms, 14:1–23, 1993.

    Article  MathSciNet  Google Scholar 

  21. H. L. Bodlaender. A tourist guide through treewidth. Acta Cybernetica, 11:1–23, 1993.

    Google Scholar 

  22. H. L. Bodlaender. Dynamic algorithms for graphs with treewidth 2. In Proceedings 19th International Workshop on Graph-Theoretic Concepts in Computer Science WG'93, pages 112–124, Berlin, 1994. Springer Verlag.

    Google Scholar 

  23. H. L. Bodlaender. On disjoint cycles. Int. J. Found. Computer Science, 5(1):59–68, 1994.

    Article  Google Scholar 

  24. H. L. Bodlaender. A linear time algorithm for finding tree-decompositions of small treewidth. SIAM J. Comput., 25:1305–1317, 1996.

    Article  Google Scholar 

  25. H. L. Bodlaender. A partial k-arboretum of graphs with bounded treewidth. Tech. Rep. UU-CS-1996-02, Dep. of Comp. Sc., Utrecht Univ., Utrecht, 1996.

    Google Scholar 

  26. H. L. Bodlaender and B. de Fluiter. Reduction algorithms for constructing solutions in graphs with small treewidth. In J.-Y. Cai and C. K. Wong, editors, Proceedings 2nd Annual International Conference on Computing and Combinatorics, COCOON'96, pages 199–208. Springer Verlag, LNCS, vol. 1090, 1996.

    Google Scholar 

  27. H. L. Bodlaender and J. Engelfriet. Domino treewidth. To appear in J. Algorithms, 1997.

    Google Scholar 

  28. H. L. Bodlaender, M. R. Fellows, and M. Hallett. Beyond NP-completeness for problems of bounded width: Hardness for the W hierarchy. In Proceedings of the 26th Annual Symposium on Theory of Computing, pages 449–458, New York, 1994. ACM Press.

    Google Scholar 

  29. H. L. Bodlaender, M. R. Fellows, M. T. Hallett, H. T. Wareham, and T. J. Warnow. The hardness of problems on thin colored graphs. Tech. Rep. UUCS-1995-36, Dep. of Comp. Sc., Utrecht Univ., Utrecht, 1995.

    Google Scholar 

  30. H. L. Bodlaender, J. R. Gilbert, H. Hafsteinsson, and T. Kloks. Approximating treewidth, pathwidth, and minimum elimination tree height. J. Algorithms, 18:238–255, 1995.

    Article  Google Scholar 

  31. H. L. Bodlaender and T. Hagerup. Parallel algorithms with optimal speedup for bounded treewidth. In Z. Fülöp and F. Gécseg, editors, Proceedings 22nd International Colloquium on Automata, Languages and Programming, pages 268–279, Berlin, 1995. Springer-Verlag, LNCS 944.

    Google Scholar 

  32. H. L. Bodlaender and T. Kloks. Efficient and constructive algorithms for the pathwidth and treewidth of graphs. J. Algorithms, 21:358–402, 1996.

    Article  Google Scholar 

  33. H. L. Bodlaender, T. Kloks, and D. Kratsch. Treewidth and pathwidth of permutation graphs. SIAM J. Disc. Meth., 8(4):606–616, 1995.

    Article  Google Scholar 

  34. H. L. Bodlaender and R. H. Möhring. The pathwidth and treewidth of cographs. SIAM J. Disc. Meth., 6:181–188, 1993.

    Article  Google Scholar 

  35. H. L. Bodlaender, R. B. Tan, D. M. Thilikos, and J. van Leeuwen. On interval routing schemes and treewidth. In M. Nagl, editor, Proceedings 21th International Workshop on Graph Theoretic Concepts in Computer Science WG'95, pages 181–186. Springer Verlag, LNCS, vol. 1017, 1995.

    Google Scholar 

  36. H. L. Bodlaender and D. M. Thilikos. Treewidth and small separators for graphs with small chordality. Tech. Rep. UU-CS-1995-02, Dep. of Comp. Sc., Utrecht Univ., Utrecht, 1995. To appear in Disc. Appl. Math.

    Google Scholar 

  37. H. L. Bodlaender and D. M. Thilikos. Constructive linear time algorithms for branchwidth. To appear in Proceedings ICALP'97, 1997.

    Google Scholar 

  38. R. B. Borie. Generation of polynomial-time algorithms for some optimization problems on tree-decomposable graphs. Algorithmica, 14:123–137, 1995.

    Article  Google Scholar 

  39. R. B. Borie, R. G. Parker, and C. A. Tovey. Deterministic decomposition of recursive graph classes. SIAM J. Disc. Meth., 4:481–501, 1991.

    Article  Google Scholar 

  40. H. Broersma, E. Dahlhaus, and T. Kloks. A linear time algorithm for minimum fill in and tree width for distance hereditary graphs. In U. Faigle and C. Hoede, editors, Scientific program 5th Twente Workshop on Graphs and Combinatorial Optimization, pages 48–50, 1997.

    Google Scholar 

  41. K. Cattell, M. J. Dinneen, and M. R. Fellows. Obstructions to within a few vertices or edges of acyclic. In Proceedings 4th Int. Workshop on Algorithms and Data Structures. Springer Verlag, LNCS, vol. 955, 1995.

    Google Scholar 

  42. K. Cattell, M. J. Dinneen, and M. R. Fellows. A simple linear-time algorithm for finding path-decompositions of small width. Inform. Proc. Letters, 57:197–204, 1996.

    Article  Google Scholar 

  43. N. Chandrasekharan and S. T. Hedetniemi. Fast parallel algorithms for tree decomposing and parsing partial k-trees. In Proc. 26th Annual Allerton Conference on Communication, Control, and Computing, Urbana-Champaign, Illinois, 1988.

    Google Scholar 

  44. S. Chaudhuri and C. D. Zaroliagis. Optimal parallel shortest paths in small treewidth digraphs. In P. Spirakis, editor, Proceedings 3rd Annual European Symposium on Algorithms ESA'95, pages 31–45. Incs979, 1995.

    Google Scholar 

  45. R. F. Cohen, S. Sairam, R. Tamassia, and J. S. Vitter. Dynamic algorithms for optimization problems in bounded tree-width graphs. In Proceedings of the 3rd Conference on Integer Programming and Combinatorial Optimization, pages 99–112, 1993.

    Google Scholar 

  46. W. Cook and P. D. Seymour. An algorithm for the ring-routing problem. Bellcore technical memorandum, Bellcore, 1993.

    Google Scholar 

  47. B. Courcelle. The monadic second-order logic of graphs II: Infinite graphs of bounded width. Mathematical Systems Theory, 21:187–221, 1989.

    Article  Google Scholar 

  48. B. Courcelle. Graph rewriting: an algebraic and logical approach. In J. van Leeuwen, editor, Handbook of Theoretical Computer Science, volume B, pages 192–242, Amsterdam, 1990. North Holland Publ. Comp.

    Google Scholar 

  49. B. Courcelle. The monadic second-order logic of graphs I: Recognizable sets of finite graphs. Information and Computation, 85:12–75, 1990.

    Article  Google Scholar 

  50. B. Courcelle. The monadic second-order logic of graphs V: On closing the gap between definability and recognizability. Theor. Comp. Sc., 80:153–202, 1991.

    Article  Google Scholar 

  51. B. Courcelle. The monadic second-order logic of graphs III: Treewidth, forbidden minors and complexity issues. Informatique Théorique, 26:257–286, 1992.

    Google Scholar 

  52. B. Courcelle and J. Lagergren. Equivalent definitions of recognizability for sets of graphs of bounded tree-width. Mathematical Structures in Computer Science, 6:141–166, 1996.

    Google Scholar 

  53. B. Courcelle and M. Mosbah. Monadic second-order evaluations on treedecomposable graphs. Theor. Comp. Sc., 109:49–82, 1993.

    Article  Google Scholar 

  54. B. de Fluiter. Algorithms for Graphs of Small Treewidth. PhD thesis, Utrecht Univ., 1997.

    Google Scholar 

  55. B. de Fluiter and H. L. Bodlaender. Parallel algorithms for treewidth two, 1997. To appear in Proceedings WG'97.

    Google Scholar 

  56. M. J. Dinneen. Bounded Combinatorial Width and Forbidden Substructures. PhD thesis, Univ. of Victoria, 1995.

    Google Scholar 

  57. R. G. Downey and M. R. Fellows. Fixed-parameter tractability and completeness III: Some structural aspects of the W hierarchy. In K. Ambos-Spies, S. Homer, and U. Schöning, editors, Complexity Theory, pages 191–226. Cambridge Univ. Press, 1993.

    Google Scholar 

  58. R. G. Downey and M. R. Fellows. Fixed-parameter tractability and completeness I: Basic results. SIAM J. Comput., 24:873–921, 1995.

    Article  Google Scholar 

  59. R. G. Downey and M. R. Fellows. Fixed-parameter tractability and completeness II: On completeness for W[1]. Theor. Comp. Sc., 141:109–131, 1995.

    Article  Google Scholar 

  60. J. A. Ellis, I. H. Sudborough, and J. Turner. The vertex separation and search number of a graph. Information and Computation, 113:50–79, 1994.

    Article  Google Scholar 

  61. D. Eppstein. Subgraph isomorphism in planar graphs and related problems. In Proceedings SODA'95, 1995.

    Google Scholar 

  62. M. R. Fellows and M. A. Langston. Nonconstructive advances in polynomial-time complexity. Inform. Proc. Letters, 26:157–162, 1987.

    Article  Google Scholar 

  63. M. R. Fellows and M. A. Langston. Nonconstructive tools for proving polynomialtime decidability. J. ACM, 35:727–739, 1988.

    Article  Google Scholar 

  64. M. R. Fellows and M. A. Langston. On search, decision and the efficiency of polynomial-time algorithms. In Proceedings of the 21rd Annual Symposium on Theory of Computing, pages 501–512, 1989.

    Google Scholar 

  65. M. R. Fellows and M. A. Langston. Fast search algorithms for layout permutation problems. Int. J. on Computer Aided VLSI Design, 3:325–340, 1991.

    Google Scholar 

  66. M. R. Fellows and M. A. Langston. On well-partial-order theory and its application to combinatorial problems of VLSI design. SIAM J. Disc. Meth., 5:117–126, 1992.

    Article  Google Scholar 

  67. M. R. Fellows and M. A. Langston. On search, decision and the efficiency of polynomial-time algorithms. J. Comp. Syst. Sc., 49:769–779, 1994.

    Article  Google Scholar 

  68. D. Fernández-Baca and A. Medipalli. Parametric module allocation on partial k-trees. IEEE Trans. on Computers, 42:738–742, 1993.

    Article  Google Scholar 

  69. D. Fernández-Baca and G. Slutzki. Parametic problems on graphs of bounded treewidth. J. Algorithms, 16:408–430, 1994.

    Article  Google Scholar 

  70. G. N. Frederickson. Maintaining regular properties dynamically in k-terminal graphs. Manuscript. To appear in Algorithmica., 1993.

    Google Scholar 

  71. G. N. Frederickson and R. Janardan. Designing networks with compact routing tables. Algorithmica, 3:171–190, 1988.

    Article  MathSciNet  Google Scholar 

  72. R. Garbe. Tree-width and path-width of comparability graphs of interval orders. In E. W. Mayr, G. Schmidt, and G. Tinhofer, editors, Proceedings 20th International Workshop on Graph Theoretic Concepts in Computer Science WG'94, pages 26–37. Springer Verlag, LNCS, vol. 903, 1995.

    Google Scholar 

  73. C. Gavoille. On the dilation of interval routing. In: Proceedings MFCS'97, 1997.

    Google Scholar 

  74. K. Y. Gorbunov. An estimate of the tree-width of a graph which has not a given planar grid as a minor. Manuscript, 1993.

    Google Scholar 

  75. D. Granot and D. Skorin-Kapov. NC algorithms for recognizing partial 2-trees and 3-trees. SIAM J. Disc. Meth., 4(3):342–354, 1991.

    Article  Google Scholar 

  76. A. Gupta and N. Nishimura. The complexity of subgraph isomorphism: Duality results for graphs of bounded path-and tree-width. Tech. Rep. CS-95-14, Univ. of Waterloo, Comp. Sc. Dep., Waterloo, Ontario, Canada, 1995.

    Google Scholar 

  77. E. M. Gurari and I. H. Sudborough. Improved dynamic programming algorithms for bandwidth minimization and the mincut linear arrangement problem. J. Algorithms, 5:531–546, 1984.

    Article  Google Scholar 

  78. J. Gustedt. On the pathwidth of chordal graphs. Disc. Appl. Math., 45(3):233–248, 1993.

    Article  Google Scholar 

  79. M. Habib and R. H. Möhring. Treewidth of cocomparability graphs and a new order-theoretic parameter. ORDER, 1:47–60, 1994.

    Article  Google Scholar 

  80. T. Hagerup. Dynamic algorithms for graphs of bounded treewidth. To appear in Proceedings ICALP'97, 1997.

    Google Scholar 

  81. T. Hagerup, J. Katajainen, N. Nishimura, and P. Ragde. Characterizations of k-terminal flow networks and computing network flows in partial k-trees. In Proceedings SODA'95, 1995.

    Google Scholar 

  82. K. Jansen and P. Scheffler. Generalized coloring for tree-like graphs. In Proceedings 18th International Workshop on Graph-Theoretic Concepts in Computer Science WG'92, pages 50–59, Berlin, 1993. Springer Verlag, LNCS, vol. 657.

    Google Scholar 

  83. D. Kaller. Definability equals recognizability of partial 3-trees. In Proceedings 22nd International Workshop on Graph-Theoretic Concepts in Computer Science WG'96, pages 239–253. Springer Verlag, LNCS, vol. 1197, 1997.

    Google Scholar 

  84. H. Kaplan and R. Shamir. Pathwidth, bandwidth and completion problems to proper interval graphs with small cliques. SIAM J. Comput., 25:540–561, 1996.

    Article  Google Scholar 

  85. H. Kaplan, R. Shamir, and R. E. Tarjan. Tractability of parameterized completion problems on chordal and interval graphs: Minimum fill-in and physical mapping. In Proceedings of the 35th annual symposium on Foundations of Computer Science (FOCS), pages 780–791. IEEE Computer Science Press, 1994.

    Google Scholar 

  86. N. G. Kinnersley and M. A. Langston. Obstruction set isolation for the gate matrix layout problem. Disc. Appl. Math., 54:169–213, 1994.

    Article  Google Scholar 

  87. T. Kloks. Treewidth of circle graphs. In Proceedings Forth International Symposium on Algorithms and Computation, ISAAC'93, pages 108–117, Berlin, 1993. Springer Verlag, LNCS, vol. 762.

    Google Scholar 

  88. T. Kloks. Treewidth. Computations and Approximations. LNCS, Vol. 842. Springer-Verlag, Berlin, 1994.

    Google Scholar 

  89. T. Kloks and D. Kratsch. Treewidth of chordal bipartite graphs. J. Algorithms, 19:266–281, 1995.

    Article  Google Scholar 

  90. E. Korach and N. Solel. Linear time algorithm for minimum weight Steiner tree in graphs with bounded treewidth. Manuscript, 1990.

    Google Scholar 

  91. A. Kornai and Z. Tuza. Narrowness, pathwidth, and their application in natural language processing. Disc. Appl. Math., 36:87–92, 1992.

    Article  Google Scholar 

  92. J. Lagergren. Efficient parallel algorithms for graphs of bounded tree-width. J. Algorithms, 20:20–44, 1996.

    Article  Google Scholar 

  93. S. J. Lauritzen and D. J. Spiegelhalter. Local computations with probabilities on graphical structures and their application to expert systems. J. of the Royal Statistical Society. Series B (Methodological), 50:157–224, 1988.

    Google Scholar 

  94. S. Mahajan and J. G. Peters. Regularity and locality in k-terminal graphs. Disc. Appl. Math., 54:229–250, 1994.

    Article  Google Scholar 

  95. E. Mata-Montero. Resilience of partial k-tree networks with edge and node failures. Networks, 21:321–344, 1991.

    Google Scholar 

  96. J. Matoušek and R. Thomas. On the complexity of finding iso-and other morphisms for partial k-trees. Disc. Math., 108:343–364, 1992.

    Article  Google Scholar 

  97. B. Monien. The bandwidth minimization problem for caterpillars with hair length 3 is NP-complete. SIAM J. Alg. Disc. Meth., 7:505–512, 1986.

    Google Scholar 

  98. A. Parra. Structural and Algorithmic Aspects of Chordal Graph Embeddings. PhD thesis, Tech. Univ. Berlin, 1996.

    Google Scholar 

  99. S. Ramachandramurthi. Algorithms for VLSI Layout Based on Graph Width Metrics. PhD thesis, Comp. Sc. Dep., Univ. of Tennessee, Knoxville, Tennessee, USA, 1994.

    Google Scholar 

  100. S. Ramachandramurthi. The structure and number of obstructions to treewidth. SIAM J. Disc. Meth., 10:146–157, 1997.

    Article  Google Scholar 

  101. N. Robertson and P. D. Seymour. Graph minors. XX. Wagner's conjecture. In prepartion.

    Google Scholar 

  102. N. Robertson and P. D. Seymour. Graph minors. I. Excluding a forest. J. Comb. Theory Series B, 35:39–61, 1983.

    Google Scholar 

  103. N. Robertson and P. D. Seymour. Graph minors. III. Planar tree-width. J. Comb. Theory Series B, 36:49–64, 1984.

    Article  Google Scholar 

  104. N. Robertson and P. D. Seymour. Graph minors. II. Algorithmic aspects of treewidth. J. Algorithms, 7:309–322, 1986.

    Article  Google Scholar 

  105. N. Robertson and P. D. Seymour. Graph minors. V. Excluding a planar graph. J. Comb. Theory Series B, 41:92–114, 1986.

    Article  Google Scholar 

  106. N. Robertson and P. D. Seymour. Graph minors. VI. Disjoint paths across a disc. J. Comb. Theory Series B, 41:115–138, 1986.

    Article  Google Scholar 

  107. N. Robertson and P. D. Seymour. Graph minors. VII. Disjoint paths on a surface. J. Comb. Theory Series B, 45:212–254, 1988.

    Article  Google Scholar 

  108. N. Robertson and P. D. Seymour. Graph minors. IV. Tree-width and well-quasiordering. J. Comb. Theory Series B, 48:227–254, 1990.

    Article  Google Scholar 

  109. N. Robertson and P. D. Seymour. Graph minors. IX. Disjoint crossed paths. J. Comb. Theory Series B, 49:40–77, 1990.

    Article  Google Scholar 

  110. N. Robertson and P. D. Seymour. Graph minors. VIII. A Kuratowski theorem for general surfaces. J. Comb. Theory Series B, 48:255–288, 1990.

    Article  Google Scholar 

  111. N. Robertson and P. D. Seymour. Graph minors. X. Obstructions to tree-decomposition. J. Comb. Theory Series B, 52:153–190, 1991.

    Article  Google Scholar 

  112. N. Robertson and P. D. Seymour. Graph minors. XVI. Excluding a non-planar graph. Manuscript, 1991.

    Google Scholar 

  113. N. Robertson and P. D. Seymour. Graph minors. XVII. Taming a vortex. Manuscript, 1991.

    Google Scholar 

  114. N. Robertson and P. D. Seymour. Graph minors. XXI. Graphs woth unique linkages. Manuscript, 1992.

    Google Scholar 

  115. N. Robertson and P. D. Seymour. Graph minors. XXII. Irrelevant vertices in linkage problems. Manuscript, 1992.

    Google Scholar 

  116. N. Robertson and P. D. Seymour. Graph minors. XI. Distance on a surface. J. Comb. Theory Series B, 60:72–106, 1994.

    Article  Google Scholar 

  117. N. Robertson and P. D. Seymour. Graph minors. XII. Excluding a non-planar graph. J. Comb. Theory Series B, 64:240–272, 1995.

    Article  Google Scholar 

  118. N. Robertson and P. D. Seymour. Graph minors. XIII. The disjoint paths problem. J. Comb. Theory Series B, 63:65–110, 1995.

    Article  Google Scholar 

  119. N. Robertson and P. D. Seymour. Graph minors. XIV. Extending an embedding. J. Comb. Theory Series B, 65:23–50, 1995.

    Article  Google Scholar 

  120. N. Robertson and P. D. Seymour. Graph minors. XV. Giant steps. J. Comb. Theory Series B, 68:112–148, 1996.

    Article  Google Scholar 

  121. N. Robertson, P. D. Seymour, and R. Thomas. Quickly excluding a planar graph. J. Comb. Theory Series B, 62:323–348, 1994.

    Article  Google Scholar 

  122. D. P. Sanders. On linear recognition of tree-width at most four. SIAM J. Disc. Meth., 9(1):101–117, 1996.

    Article  Google Scholar 

  123. A. Satyanarayana and L. Tung. A characterization of partial 3-trees. Networks, 20:299–322, 1990.

    Google Scholar 

  124. J. B. Saxe. Dynamic programming algorithms for recognizing small-bandwidth graphs in polynomial time. SIAM J. Alg. Disc. Meth., 1:363–369, 1980.

    Google Scholar 

  125. P. Schefüer. A practical linear time algorithm for disjoint paths in graphs with bounded tree-width. Report 396/1994, TU Berlin, Fachbereich Mathematik, Berlin, 1994.

    Google Scholar 

  126. P. D. Seymour and R. Thomas. Call routing and the ratcatcher. Combinatorica, 14(2):217–241, 1994.

    Article  Google Scholar 

  127. R. Sundaram, K. Sher Singh, and C. Pandu Rangan. Treewidth of circular-arc graphs. SIAM J. Disc. Meth., 7:647–655, 1994.

    Article  Google Scholar 

  128. A. Takahashi, S. Ueno, and Y. Kajitani. Minimal acyclic forbidden minors for the family of graphs with bounded path-width. Disc. Math., 127(1/3):293–304, 1994.

    Article  Google Scholar 

  129. J. Telle and A. Proskurowski. Efficient sets in partial k-trees. Disc. Appl. Math., 44:109–117, 1993.

    Article  Google Scholar 

  130. J. Telle and A. Proskurowski. Practical algorithms on partial k-trees with an application to domination-like problems. In Proceedings of Workshop on Algorithms and Data Structures WADS'93, pages 610–621. Springer Verlag, LNCS, vol. 700, 1993.

    Google Scholar 

  131. M. Thorup. Structured programs have small tree-width and good register allocation. Tech. Rep. DIKU-TR-95/18, Dep. of Comp. Sc., Univ. of Copenhagen, Denmark, 1995. To appear in: Proceedings WG'97.

    Google Scholar 

  132. E. Wanke. Bounded tree-width and LOGCFL. J. Algorithms, 16:470–491, 1994.

    Article  Google Scholar 

  133. T. V. Wimer. Linear Algorithms on k-Terminal Graphs. PhD thesis, Dept. of Comp. Sc., Clemson Univ., 1987.

    Google Scholar 

  134. X. Zhou, S. Nakano, and T. Nishizeki. Edge-coloring partial k-trees. J. Algorithms, 21:598–617, 1996.

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science, Utrecht University, P.O. Box 80.089, 3508, TB Utrecht, the Netherlands

    Hans L. Bodlaender

Authors
  1. Hans L. Bodlaender
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Igor Prívara Peter Ružička

Rights and permissions

Reprints and permissions

Copyright information

© 1997 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Bodlaender, H.L. (1997). Treewidth: Algorithmic techniques and results. In: Prívara, I., Ružička, P. (eds) Mathematical Foundations of Computer Science 1997. MFCS 1997. Lecture Notes in Computer Science, vol 1295. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0029946

Download citation

  • DOI: https://doi.org/10.1007/BFb0029946

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-63437-9

  • Online ISBN: 978-3-540-69547-9

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics

Search

Navigation