2003/08/01 by William J. Cook, Paul Seymour · 178 citations
Computer Science · Engineering · Mathematics · #Advanced Graph Theory Research #Vehicle Routing Optimization Methods #Complexity and Algorithms in Graphs #Travelling salesman problem #Heuristics #Lin–Kernighan heuristic #Branch and bound #Combinatorial optimization #Heuristic #Graph #Invariant (physics) #Mathematical optimization #Computer science #Mathematics #2-opt #Algorithm #Theoretical computer science
paper · doi:10.1287/ijoc.15.3.233.16078
published in INFORMS journal on computing 15(3), 233-248 (Institute for Operations Research and the Management Sciences)
openalex publication_date 2003/08/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/07
Robertson and Seymour introduced branch-width as a new 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 describe a heuristic method for finding branch decompositions; the method is based on the eigenvector technique for finding graph separators. We use this as a tool to obtain high-quality tours for the traveling salesman problem by merging collections of tours produced by standard traveling salesman heuristics.