Department of Applied Mathematics & Physics, Kyoto University
Technical Report 2012-009 (December 4, 2012)
An Exact Algorithm for TSP in Degree-3 Graphs via Circuit Procedure and Amortization on Connectivity Structure
by Mingyu Xiao and Hiroshi Nagamochi
The paper presents an $O^*(1.2312^n)$-time and polynomial- space algorithm for the traveling salesman problem
in an $n$-vertex graph with maximum degree $3$.
This improves the previous time bounds of
$O^*(1.251^n)$ by Iwama and Nakashima and $O^*(1.260^n)$ by Eppstein.
Our algorithm is a simple branch-and-search algorithm.
The only branch rule is designed on a cut-circuit structure of a graph
induced by unprocessed edges.
To improve a time bound by a simple analysis on measure and conquer,
we introduce an amortization scheme over the cut-circuit structure
by defining the measure of an instance
to be the sum of not only weights of vertices but also
weights of connected components of the induced graph.