William Cook, Optimization via Branch Decomposition

Robertson and Seymour introduced branch-width as a connectivity invariant of graphs in their proof of the Wagner conjecture. Decompositions based on this invariant provide a natural framework for implementing dynamic-programming algorithms to solve graph optimization problems. We will discuss the computational issues involved in using branch-width as as a general tool in discrete optimization.