An Improved Exact Algorithm for TSP in Graphs of Maximum Degree 4

作者：Xiao, Mingyu^*; Nagamochi, Hiroshi

来源：Theory of Computing Systems, 2016, 58(2): 241-272.

DOI：10.1007/s00224-015-9612-x

• Traveling salesman problem
• Exact exponential algorithm
• Graph algorithm
• Measure-and-conquer

The paper presents a 1.692(n)n(O(1))-time polynomial-space algorithm for the traveling salesman problem in an n-vertex edge-weighted graph with maximum degree 4, which improves the previous results of the 1.890(n)n(O(1))-time polynomial-space algorithm by Eppstein and the 1.733(n)n(O(1))-time exponential-space algorithm by Gebauer.

• 出版日期2016-2
• 单位电子科技大学