Department of Applied Mathematics & Physics, Kyoto University
Technical Report 2015-003 (June 30, 2015)
A Polynomial-space Exact Algorithm for TSP in Degree-6 Graphs
by Norhazwani Md Yunos, Aleksandar Shurbevski, Hiroshi Nagamochi
This paper presents the first polynomial-space exact algorithm
for TSP in graphs with degree at most~6.
We develop a set of branching rules to aid the analysis of the branching
we use the measure-and-conquer method to effectively analyze our
and we obtain a running time of $O^*(2.7467^n)$,
still advantageous over other known polynomial-space algorithms
for the TSP in general graphs.