科研之友
微信
新浪微博
Facebook
分享链接
摘要
The paper presents an -time and polynomial-space algorithm for the traveling salesman problem in an -vertex graph with maximum degree 3. This improves all previous time bounds of polynomial-space algorithms for this problem. Our algorithm is a simple branch-and-search algorithm with only one branch rule 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.
- 出版日期2016-2
- 单位电子科技大学
