A Polynomial-Space Exact Algorithm for TSP in Degree-6 Graphs
A Polynomial-Space Exact Algorithm for TSP in Degree-6 Graphs
复制标题
DOI：
10.1007/978-3-319-48532-4_20
复制
发表时间：
2015-09
期刊：
影响因子：
--
通讯作者：
N. M. Yunos;Aleksandar Shurbevski;H. Nagamochi
中科院分区：
文献类型：
--
作者：
N. M. Yunos;Aleksandar Shurbevski;H. Nagamochi
本文提出了第一个多项式空间精确算法，专门用于解决度不超过6的图中的TSP问题。我们开发了一套分支规则，以帮助分析的分支算法。使用测量和征服的方法，我们表明，当应用到ann顶点图的度最多为6，该算法的运行时间为，这仍然是优于其他已知的多项式空间算法的一般图的TSP。
This paper presents the first polynomial-space exact algorithm specialized for the TSP in graphs with degree at most 6. We develop a set of branching rules to aid the analysis of the branching algorithm. Using the measure-and-conquer method, we show that when applied to ann-vertex graph with degree at most 6, the algorithm has a running time of, which is still advantageous over other known polynomial-space algorithms for the TSP in general graphs.