[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Skip to main content
Springer Nature Link
Log in

Treewidth: Structure and Algorithms

  • Conference paper
Structural Information and Communication Complexity (SIROCCO 2007)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 4474))

Abstract

This paper surveys some aspects of the graph theoretic notion of treewidth. In particular, we look at the interaction between different characterizations of the notion, and algorithms and algorithmic applications.

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.

Similar content being viewed by others

References

  1. Arnborg, S.: Efficient algorithms for combinatorial problems on graphs with bounded decomposability – A survey. BIT 25, 2–23 (1985)

    Article  MathSciNet  MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

  3. Arnborg, S., et al.: An algebraic theory of graph reduction. J. ACM 40, 1134–1164 (1993)

    Article  MathSciNet  MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

  7. Bachoore, E.H., Bodlaender, H.L.: A branch and bound algorithm for exact, upper, and lower bounds on treewidth. In: Cheng, S.-W., Poon, C.K. (eds.) AAIM 2006. LNCS, vol. 4041, pp. 255–266. Springer, Heidelberg (2006)

    Chapter  Google Scholar 

  8. Bauderon, M., Courcelle, B.: Graph expressions and graph rewritings. Mathematical Systems Theory 20, 83–127 (1987)

    Article  MathSciNet  MATH  Google Scholar 

  9. Bellenbaum, P., Diestel, R.: Two short proofs concerning tree-decompositions. Combinatorics, Probability, and Computing 11, 541–547 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  10. Berry, A., Bordat, J.-P., Cogis, O.: Generating all the minimal separators of a graph. Int. J. Found. Computer Science 11, 397–404 (2000)

    Article  MathSciNet  Google Scholar 

  11. Bienstock, D.: Graph searching, path-width, tree-width and related problems (a survey). In: Reliability Of Computer And Communication Network. DIMACS Ser. in Discrete Mathematics and Theoretical Computer Science, vol. 5, pp. 33–49 (1991)

    Google Scholar 

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

    MathSciNet  MATH  Google Scholar 

  13. Bodlaender, H.L.: A partial k-arboretum of graphs with bounded treewidth. Theor. Comp. Sc. 209, 1–45 (1998)

    Article  MathSciNet  MATH  Google Scholar 

  14. Bodlaender, H.L.: Discovering treewidth. In: Vojtáš, P., et al. (eds.) SOFSEM 2005. LNCS, vol. 3381, pp. 1–16. Springer, Heidelberg (2005)

    Google Scholar 

  15. Bodlaender, H.L.: Treewidth: Characterizations, applications, and computations. In: Fomin, F.V. (ed.) WG 2006. LNCS, vol. 4271, pp. 1–14. Springer, Heidelberg (2006)

    Chapter  Google Scholar 

  16. Bodlaender, H.L., et al.: On exact algorithms for treewidth. In: Azar, Y., Erlebach, T. (eds.) ESA 2006. LNCS, vol. 4168, pp. 672–683. Springer, Heidelberg (2006)

    Chapter  Google Scholar 

  17. Bodlaender, H.L., Grigoriev, A., Koster, A.M.C.A.: Treewidth lower bounds with brambles. In: Brodal, G.S., Leonardi, S. (eds.) ESA 2005. LNCS, vol. 3669, pp. 391–402. Springer, Heidelberg (2005)

    Chapter  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

  19. Bodlaender, H.L., Koster, A.M.C.A., van de Eijkhof, F.: Pre-processing rules for triangulation of probabilistic networks. Computational Intelligence 21(3), 286–305 (2005)

    Article  MathSciNet  Google Scholar 

  20. Bodlaender, H.L., van Antwerpen-de Fluiter, B.: Parallel algorithms for series parallel graphs and graphs with treewidth two. Algorithmica 29, 543–559 (2001)

    Google Scholar 

  21. Bodlaender, H.L., et al.: On interval routing schemes and treewidth. Information and Computation 139(1), 92–109 (1997)

    Article  MathSciNet  MATH  Google Scholar 

  22. Borie, R.B.: Recursively Constructed Graph Families. PhD thesis, School of Information and Computer Science, Georgia Institute of Technology (1988)

    Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

  24. Borie, R.B., Parker, R.G., Tovey, C.A.: Deterministic decomposition of recursive graph classes. SIAM J. Disc. Math. 4, 481–501 (1991)

    Article  MathSciNet  MATH  Google Scholar 

  25. 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)

    Article  MathSciNet  MATH  Google Scholar 

  26. Bouchitté, V., Todinca, I.: Treewidth and minimum fill-in: Grouping the minimal separators. SIAM J. Comput. 31, 212–232 (2001)

    Article  MathSciNet  MATH  Google Scholar 

  27. Bouchitté, V., Todinca, I.: Listing all potential maximal cliques of a graph. Theor. Comp. Sc. 276, 17–32 (2002)

    Article  MATH  Google Scholar 

  28. Clautiaux, F., et al.: Heuristic and meta-heuristic methods for computing graph treewidth. RAIRO Operations Research 38, 13–26 (2004)

    Article  MathSciNet  MATH  Google Scholar 

  29. Cockayne, E.J., Goodman, S.E., Hedetniemi, S.T.: A linear algorithm for the domination number of a tree. Information Processing Letters 4, 41–44 (1975)

    Article  MATH  Google Scholar 

  30. Colbourn, C.J., Stewart, L.K.: Dominating cycles in series-parallel graphs. Ars Combinatorica 19A, 107–112 (1985)

    MathSciNet  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

  32. Courcelle, B., Mosbah, M.: Monadic second-order evaluations on tree-decomposable graphs. Theor. Comp. Sc. 109, 49–82 (1993)

    Article  MathSciNet  MATH  Google Scholar 

  33. Daykin, D.E., Ng, C.P.: Algorithms for generalized stability numbers of tree graphs. J. Austral. Math. Soc. 6, 89–100 (1966)

    MathSciNet  MATH  Google Scholar 

  34. Demaine, E.D., Hajiaghayi, M.: The bidimensionality theory and its algorithmic applications. Unpublished manuscript (2006)

    Google Scholar 

  35. Dendris, N.D., Kirousis, L.M., Thilikos, D.M.: Fugitive-search games on graphs and related parameters. Theor. Comp. Sc. 172, 233–254 (1997)

    Article  MathSciNet  MATH  Google Scholar 

  36. Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer, Heidelberg (1998)

    MATH  Google Scholar 

  37. Duffin, R.J.: Topology of series-parallel graphs. J. Math. Anal. Appl. 10, 303–318 (1965)

    Article  MathSciNet  MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

  39. Fellows, M.R., Langston, M.A.: Nonconstructive advances in polynomial-time complexity. Information Processing Letters 26, 157–162 (1987)

    Article  MathSciNet  MATH  Google Scholar 

  40. Fellows, M.R., Langston, M.A.: Nonconstructive tools for proving polynomial-time decidability. J. ACM 35, 727–739 (1988)

    Article  MathSciNet  MATH  Google Scholar 

  41. Fomin, F.V., Kratsch, D., Todinca, I.: Exact (exponential) algorithms for treewidth and minimum fill-in. In: Díaz, J., et al. (eds.) ICALP 2004. LNCS, vol. 3142, pp. 568–580. Springer, Heidelberg (2004)

    Google Scholar 

  42. Franklin, M., Galil, Z., Yung, M.: Eavesdropping games: A graph-theoretic approach to privacy in distributed systems. J. ACM 47, 225–243 (2000)

    Article  MathSciNet  MATH  Google Scholar 

  43. Gavril, F.: The intersection graphs of subtrees in trees are exactly the chordal graphs. J. Comb. Theory Series B 16, 47–56 (1974)

    Article  MathSciNet  MATH  Google Scholar 

  44. Gogate, V., Dechter, R.: A complete anytime algorithm for treewidth. In: Proceedings of the 20th Annual Conference on Uncertainty in Artificial Intelligence UAI-04, Arlington, Virginia, USA, pp. 201–208. AUAI Press (2004)

    Google Scholar 

  45. Golumbic, M.C.: Algorithmic Graph Theory and Perfect Graphs. Academic Press, New York (1980)

    MATH  Google Scholar 

  46. Gu, Q.-P., Tamaki, H.: Optimal branch-decomposition of planar graphs in O(n 3) time. In: Caires, L., et al. (eds.) ICALP 2005. LNCS, vol. 3580, pp. 373–384. Springer, Heidelberg (2005)

    Google Scholar 

  47. Habel, A., Kreowski, H.J.: Characteristics of graph languages generated by edge replacement. Theor. Comp. Sc. 51, 81–115 (1987)

    Article  MathSciNet  MATH  Google Scholar 

  48. Habel, A., Kreowski, H.J.: May we introduce to you: hyperedge replacement. In: Ehrig, H., et al. (eds.) Graph Grammars 1986. LNCS, vol. 291, pp. 15–26. Springer, Heidelberg (1987)

    Google Scholar 

  49. Hare, E., et al.: Linear-time computability of combinatorial problems on generalized-series-parallel graphs. In: Johnson, D.S., et al. (eds.) Proc. of the Japan-US Joint Seminar on Discrete Algorithms and Complexity, Orlando, Florida, Academic Press, London (1987)

    Google Scholar 

  50. Hassin, R., Tamir, A.: Efficient algorithms for optimization and selection on series-parallel graphs. SIAM J. Alg. Disc. Meth. 7, 379–389 (1986)

    Article  MathSciNet  MATH  Google Scholar 

  51. Held, M., Karp, R.: A dynamic programming approach to sequencing problems. J. SIAM 10, 196–210 (1962)

    MathSciNet  MATH  Google Scholar 

  52. Hicks, I.V.: Planar branch decompositions I: The ratcatcher. INFORMS J. on Computing 17, 402–412 (2005)

    Article  MathSciNet  Google Scholar 

  53. Hicks, I.V.: Planar branch decompositions II: The cycle method. INFORMS J. on Computing 17, 413–421 (2005)

    Article  MathSciNet  Google Scholar 

  54. Hicks, I.V., Koster, A.M.C.A., Kolotoğlu, E.: Branch and tree decomposition techniques for discrete optimization. In: Smith, J.C. (ed.) TutORials 2005, INFORMS Annual Meeting. INFORMS Tutorials in Operations Research Series, pp. 1–29 (2005)

    Google Scholar 

  55. Hliněný, P., et al.: Width parameters beyond tree-width and their applications. Paper to appear in this special issue (2006)

    Google Scholar 

  56. Kikuno, T., Yoshida, N., Kakuda, Y.: A linear algorithm for the domination number of a series-parallel graph. Disc. Appl. Math. 5, 299–311 (1983)

    Article  MathSciNet  MATH  Google Scholar 

  57. Kinnersley, N.G.: The vertex separation number of a graph equals its path width. Information Processing Letters 42, 345–350 (1992)

    Article  MathSciNet  MATH  Google Scholar 

  58. Kirousis, L.M., Papadimitriou, C.H.: Interval graphs and searching. Disc. Math. 55, 181–184 (1985)

    Article  MathSciNet  MATH  Google Scholar 

  59. Kleinberg, J., Tardos, É.: Algorithm Design. Addison-Wesley, Boston (2005)

    Google Scholar 

  60. Kloks, T., Kratsch, D.: Listing all minimal separators of a graph. SIAM J. Comput. 27(3), 605–613 (1998)

    Article  MathSciNet  MATH  Google Scholar 

  61. Koster, A.M.C.A., van Hoesel, S.P.M., Kolen, A.W.J.: Solving partial constraint satisfaction problems with tree decomposition. Networks 40(3), 170–180 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  62. Lapoire, D.: Recognizability equals definability, for every set of graphs of bounded tree-width. In: Meinel, C., Morvan, M. (eds.) STACS 1998. LNCS, vol. 1373, pp. 618–628. Springer, Heidelberg (1998)

    Chapter  Google Scholar 

  63. Lautemann, C.: Efficient algorithms on context-free graph languages. In: Lepistö, T., Salomaa, A. (eds.) ICALP 1988. LNCS, vol. 317, pp. 362–378. Springer, Heidelberg (1988)

    Google Scholar 

  64. Lautemann, C.: The complexity of graph languages generated by hyperedge replacement. Acta Informatica 27, 399 (1990)

    Article  MathSciNet  MATH  Google Scholar 

  65. Matoušek, J., Thomas, R.: Algorithms for finding tree-decompositions of graphs. J. Algorithms 12, 1–22 (1991)

    Article  MathSciNet  MATH  Google Scholar 

  66. Parra, A., Scheffler, P.: Characterizations and algorithmic applications of chordal graph embeddings. Disc. Appl. Math. 79, 171–188 (1997)

    Article  MathSciNet  MATH  Google Scholar 

  67. Pfaff, J., Laskar, R., Hedetniemi, S.T.: Linear algorithms for independent domination and total domination in series-parallel graphs. Congressus Numerantium 45, 71–82 (1984)

    MathSciNet  Google Scholar 

  68. Reed, B.A.: Tree width and tangles, a new measure of connectivity and some applications. In: Surveys in Combinatorics. LMS Lecture Note Series, vol. 241, pp. 87–162. Cambridge University Press, Cambridge (1997)

    Google Scholar 

  69. Reed, B.A.: Algorithmic aspects of tree width. In: Recent Advances in Algorithms and Combinatorics. CMS Books in Mathematics, pp. 85–107. Springer, New York (2003)

    Chapter  Google Scholar 

  70. Richey, M.B.: Combinatorial optimization on series-parallel graphs: algorithms and complexity. PhD thesis, School of Industrial and Systems Engineering, Georgia Institute of Technology (1985)

    Google Scholar 

  71. Robertson, N., Seymour, P.D.: Graph minors. II. Algorithmic aspects of tree-width. J. Algorithms 7, 309–322 (1986)

    Article  MathSciNet  MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

  73. Rose, D.J., Tarjan, R.E., Lueker, G.S.: Algorithmic aspects of vertex elimination on graphs. SIAM J. Comput. 5, 266–283 (1976)

    Article  MathSciNet  MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

  75. Seymour, P.D., Thomas, R.: Graph searching and a minimax theorem for tree-width. J. Comb. Theory Series B 58, 239–257 (1993)

    Article  MathSciNet  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

  77. Skodinis, K.: Construction of linear tree-layouts which are optimal with respect to vertex separation in linear time. J. Algorithms 47, 40–59 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  78. Sysło, M.M.: Series-parallel graphs and depth-first search trees. IEEE Trans. on Circuits and Systems 31(12), 1029–1033 (1984)

    Article  MATH  Google Scholar 

  79. Takamizawa, K., Nishizeki, T., Saito, N.: Linear-time computability of combinatorial problems on series-parallel graphs. J. ACM 29, 623–641 (1982)

    Article  MathSciNet  MATH  Google Scholar 

  80. Telle, J.A., Proskurowski, A.: Algorithms for vertex partitioning problems on partial k-trees. SIAM J. Disc. Math. 10, 529–550 (1997)

    Article  MathSciNet  MATH  Google Scholar 

  81. Villanger, Y.: Improved exponential-time algorithms for treewidth and minimum fill-in. In: Correa, J.R., Hevia, A., Kiwi, M. (eds.) LATIN 2006. LNCS, vol. 3887, pp. 800–811. Springer, Heidelberg (2006)

    Chapter  Google Scholar 

  82. Wimer, T.V.: Linear algorithms for the dominating cycle problems in series-parallel graphs, 2-trees and Halin graphs. Congressus Numerantium 56 (1987)

    Google Scholar 

  83. Wimer, T.V.: Linear Algorithms on k-Terminal Graphs. PhD thesis, Dept. of Computer Science, Clemson University (1987)

    Google Scholar 

  84. Wimer, T.V., Hedetniemi, S.T., Laskar, R.: A methodology for constructing linear graph algorithms. Congressus Numerantium 50, 43–60 (1985)

    MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Institute of Information and Computing Sciences, 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

Giuseppe Prencipe Shmuel Zaks

Rights and permissions

Reprints and permissions

Copyright information

© 2007 Springer Berlin Heidelberg

About this paper

Cite this paper

Bodlaender, H.L. (2007). Treewidth: Structure and Algorithms. In: Prencipe, G., Zaks, S. (eds) Structural Information and Communication Complexity. SIROCCO 2007. Lecture Notes in Computer Science, vol 4474. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-72951-8_3

Download citation

  • DOI: https://doi.org/10.1007/978-3-540-72951-8_3

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-72918-1

  • Online ISBN: 978-3-540-72951-8

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation