|
|||||
|
|
The traveling salesman problem with few inner points |
|
| Affiliation: | a Warwick Business School, The University of Warwick, Conventry CV4 7AL, UK b Institute of Theoretical Computer Science, ETH Zurich, CH-8092 Zurich, Switzerland c Department of Mathematics and Computer Science, Technical University of Eindhoven, P.O. Box 513, 5600 MB Eindhoven, The Netherlands |
| Abstract: | We propose two algorithms for the planar Euclidean traveling salesman problem. The first runs in O(k!kn) time and O(k) space, and the second runs in O(2kk2n) time and O(2kkn) space, where n denotes the number of input points and k denotes the number of points interior to the convex hull. |
| Keywords: | Exact algorithm Fixed-parameter algorithm Parameterization Traveling salesman |
| 本文献已被 ScienceDirect 等数据库收录！ | |