The traveling salesman problem with few inner points

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

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

7 Citations (Scopus)

Abstract

We study the traveling salesman problem (TSP) in the 2-dimensional Euclidean plane. The problem is NP-hard in general, but trivial if the points are in convex position. In this paper, we investigate the influence of the number of inner points (i.e., points in the interior of the convex hull) on the computational complexity of the problem. We give two simple algorithms for this problem. The first one runs in O(k!kn) time and O(k) space, and the second runs in O(2 k k 2 n) time and O(2 k kn) space, when n is the total number of input points and k is the number of inner points. Hence, if k is taken as a parameter, this problem is fixed-parameter tractable (FPT), and also can be solved in polynomial time if k=O(log n). We also consider variants of the TSP such as the prize-collecting TSP and the partial TSP in this setting, and show that they are FPT as well.
Original languageEnglish
Title of host publicationComputing and Combinatorics (Proceedings 10th Annual International Conference, COCOON 2004, Jeju Island, Korea, August 17-20, 2004)
EditorsK.Y. Chwa, J.I. Munro
Place of PublicationBerlin
PublisherSpringer
Pages268-277
ISBN (Print)3-540-22856-X
DOIs
Publication statusPublished - 2004

Publication series

NameLecture Notes in Computer Science
Volume3106
ISSN (Print)0302-9743

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

  • Cite this

    Deineko, V. G., Hoffmann, M., Okamoto, Y., & Woeginger, G. J. (2004). The traveling salesman problem with few inner points. In K. Y. Chwa, & J. I. Munro (Eds.), Computing and Combinatorics (Proceedings 10th Annual International Conference, COCOON 2004, Jeju Island, Korea, August 17-20, 2004) (pp. 268-277). (Lecture Notes in Computer Science; Vol. 3106). Berlin: Springer. https://doi.org/10.1007/978-3-540-27798-9_30