Robertson and Seymour introduced branch-width as a new measure of the connectivity of graphs. Decompositions based on this measure provide a natural framework for implementing dynamic programming algorithms to solve graph optimization problems. In this talk we will discuss the computational
issues involved in using branch-width as as a general tool in discreteoptimization. We will present applications to traveling salesman problems, euclidean steiner tree problems, graph bipartition, maximum cut problems, maximum stable set problems, and network design problems.
