Branch and Tree Decomposition Techniques for Discrete Optimization
Abstract
This chapter gives a general overview of two emerging techniques for discrete optimization that have footholds in mathematics, computer science, and operations research: branch decompositions and tree decompositions. Branch decompositions and tree decompositions, along with their respective connectivity invariants, branchwidth and treewidth, were first introduced to aid in proving the graph minors theorem, a well-known conjecture (Wagner's conjecture Robertson and Seymour [N. Robertson and P. D. Seymour. Graph minors: A survey. I. Anderson, ed. Surveys in Combinatorics. London Mathematical Society Lecture Note Series, Vol. 103. Cambridge University Press, Cambridge, UK, 153--171, 1985.]) in graph theory. The algorithmic importance of branch decompositions and tree decompositions for solving 𝒩𝒫-hard problems modeled on graphs was first realized by computer scientists in relation to formulating graph problems in monadic second-order logic. The dynamic programming techniques utilizing branch decompositions and tree decompositions, called branch decomposition- and tree decomposition-based algorithms, fall into a class of algorithms known as fixed-parameter tractable algorithms and have been shown to be effective in a practical setting for 𝒩𝒫-hard problems such as minimum domination, the traveling salesman problem, general minor containment, and frequency assignment problems.
This publication has no references to display.
Your Access Options
-
Login Options
Purchase Options
Save for laterOther Options
Token AccessClaim access using a tokenRestore guest accessApplies for purchases made as a guest
