The traveling salesman problem with few inner points

V.G. Deineko, M. Hoffmann, Y. Okamoto, G.J. Woeginger

Research output: Contribution to journalArticleAcademicpeer-review

17 Citations (Scopus)
1 Downloads (Pure)

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.
Original languageEnglish
Pages (from-to)106-110
JournalOperations Research Letters
Volume34
Issue number1
DOIs
Publication statusPublished - 2006

Fingerprint Dive into the research topics of 'The traveling salesman problem with few inner points'. Together they form a unique fingerprint.

  • Cite this