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

pdf File

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 algorithm, and we use the measure-and-conquer method to effectively analyze our branching algorithm, 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.