iBet uBet web content aggregator. Adding the entire web to your favor.
iBet uBet web content aggregator. Adding the entire web to your favor.



Link to original content: https://doi.org/10.1007/11775096_24
A Branch and Bound Algorithm for Exact, Upper, and Lower Bounds on Treewidth | SpringerLink
Skip to main content
Springer Nature Link
Log in

A Branch and Bound Algorithm for Exact, Upper, and Lower Bounds on Treewidth

  • Conference paper
Algorithmic Aspects in Information and Management (AAIM 2006)

Part of the book series: Lecture Notes in Computer Science ((LNISA,volume 4041))

Included in the following conference series:

Abstract

In this paper, a branch and bound algorithm for computing the treewidth of a graph is presented. The method incorporates extensions of existing results, and uses new pruning and reduction rules, based upon properties of the adopted branching strategy. We discuss how the algorithm can not only be used to obtain exact bounds for the treewidth, but also to obtain upper and/or lower bounds. Computational results of the algorithm are presented.

This work has been supported by the Netherlands Organization for Scientific Research NWO (project TACO: ’Treewidth And Combinatorial Optimization’).

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

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 39.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 54.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

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. Amir, E.: Efficient approximation for triangulation of minimum treewidth. In: Proceedings of the 17th Conference on Uncertainty in Artificial Intelligence, UAI 2001, Seattle, Washington, USA, pp. 7–15 (2001)

    Google Scholar 

  2. Arnborg, S., Corneil, D.G., Proskurowski, A.: Complexity of finding embeddings in a k-tree. SIAM Journal on Algebraic and Discrete Methods 8, 277–284 (1987)

    Article  MATH  MathSciNet  Google Scholar 

  3. Bachoore, E., Bodlaender, H.L.: New heuristics for upper bound of treewidth. In: Nikoletseas, S.E. (ed.) WEA 2005. LNCS, vol. 3503, pp. 216–227. Springer, Heidelberg (2005)

    Chapter  Google Scholar 

  4. Becker, A., Geiger, D.: A sufficiently fast algorithm for finding close to optimal clique trees. Artificial Intelligence Journal 125, 3–17 (2001)

    Article  MATH  MathSciNet  Google Scholar 

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

    Article  MathSciNet  Google Scholar 

  6. Bodlaender, H.L.: Discovering treewidth. In: Vojtáš, P., Bieliková, M., Charron-Bost, B., Sýkora, O. (eds.) SOFSEM 2005. LNCS, vol. 3381, pp. 1–16. Springer, Heidelberg (2005)

    Chapter  Google Scholar 

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

    Article  MATH  MathSciNet  Google Scholar 

  8. Bodlaender, H.L.: A tourist guide through treewidth. Acta Cybernetica 11(1-2), 1–21 (1993)

    MATH  MathSciNet  Google Scholar 

  9. Bodlaender, H.L.: Necessary edges in k-chordalizations of graphs. Journal of Combinatorial Optimization 7, 283–290 (2003)

    Article  MATH  MathSciNet  Google Scholar 

  10. Bodlaender, H.L., Koster, A.M.C.A., Wolle, T.: Contraction and treewidth lower bounds. In: Albers, S., Radzik, T. (eds.) ESA 2004. LNCS, vol. 3221, pp. 628–639. Springer, Heidelberg (2004)

    Chapter  Google Scholar 

  11. van den Eijkhof, F., Bodlaender, H.L., Koster, A.M.C.A.: Safe reduction rules for weighted treewidth. In: Kučera, L. (ed.) WG 2002. LNCS, vol. 2573, pp. 176–185. Springer, Heidelberg (2002)

    Chapter  Google Scholar 

  12. Clautiaux, F., Moukrim, A., Négre, S., Carlier, J.: Heuristic and meta-heuristic methods for computing graph treewidth. RAIRO Operations Research 38, 13–26 (2004)

    Article  MATH  MathSciNet  Google Scholar 

  13. Gogate, V., Dechter, R.: A complete any time algorithm for treewidth. In: Proceedings of the 20th Conference on Uncertainty in Artificial Intelligence, Banff, Canada, pp. 201–208. AUAI Press, Arlington (2004)

    Google Scholar 

  14. Koster, A.M.C.A., Bodlaender, H.L., van Hoesel, S.: Treewidth: Computational experiments. In: Electronic Notes in Discrete Mathematics, vol. 8. Elsevier, Amsterdam (2001)

    Google Scholar 

  15. Ramachandramurthi, S.: The structure and number of obstructions to treewidth. SIAM J. Disc. Math. 10, 146–157 (1997)

    Article  MATH  MathSciNet  Google Scholar 

  16. Röhrig, H.: Tree decomposition: A feasibility study. Master’s thesis, Max-Planck-Institut für Informatik, Saarbrücken, Germany (1998)

    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

    Emgad H. Bachoore & Hans L. Bodlaender

Authors
  1. Emgad H. Bachoore
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Hans L. Bodlaender
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Department of Computer Science, Clear Water Bay, Hong Kong University of Science and Technology, Hong Kong, China

    Siu-Wing Cheng

  2. Department of Computer Science, City University of Hong Kong,  

    Chung Keung Poon

Rights and permissions

Reprints and permissions

Copyright information

© 2006 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Bachoore, E.H., Bodlaender, H.L. (2006). A Branch and Bound Algorithm for Exact, Upper, and Lower Bounds on Treewidth. In: Cheng, SW., Poon, C.K. (eds) Algorithmic Aspects in Information and Management. AAIM 2006. Lecture Notes in Computer Science, vol 4041. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11775096_24

Download citation

  • DOI: https://doi.org/10.1007/11775096_24

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-35157-3

  • Online ISBN: 978-3-540-35158-0

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation