Tour merging via branch-decomposition

Tour merging via branch-decomposition

0.00 Avg rating0 Votes
Article ID: iaor2007464
Country: United States
Volume: 15
Issue: 3
Start Page Number: 233
End Page Number: 248
Publication Date: Jun 2003
Journal: INFORMS Journal On Computing
Authors: ,
Keywords: programming: dynamic, heuristics
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.