| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 1143465 | Operations Research Letters | 2006 | 5 Pages |
Abstract
We propose two algorithms for the planar Euclidean traveling salesman problem. The first runs in O(k!kn)O(k!kn) time and O(k)O(k) space, and the second runs in O(2kk2n)O(2kk2n) time and O(2kkn)O(2kkn) space, where nn denotes the number of input points and kk denotes the number of points interior to the convex hull.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Vladimir G. Deı˘neko, Michael Hoffmann, Yoshio Okamoto, Gerhard J. Woeginger,