The traveling salesman problem with few inner points

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

doi:10.1016/j.orl.2005.01.002

The traveling salesman problem with few inner points

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

Research output: Contribution to journal › Article › Academic › peer-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 language	English
Pages (from-to)	106-110
Journal	Operations Research Letters
Volume	34
Issue number	1
DOIs	https://doi.org/10.1016/j.orl.2005.01.002
Publication status	Published - 2006

Access to Document

10.1016/j.orl.2005.01.002

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. (2006). The traveling salesman problem with few inner points. Operations Research Letters, 34(1), 106-110. https://doi.org/10.1016/j.orl.2005.01.002

@article{7c4abf9d8e6345e2b0ba770321d27561,

title = "The traveling salesman problem with few inner points",

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.",

author = "V.G. Deineko and M. Hoffmann and Y. Okamoto and G.J. Woeginger",

year = "2006",

doi = "10.1016/j.orl.2005.01.002",

language = "English",

volume = "34",

pages = "106--110",

journal = "Operations Research Letters",

issn = "0167-6377",

publisher = "Elsevier",

number = "1",

}

TY - JOUR

T1 - The traveling salesman problem with few inner points

AU - Deineko, V.G.

AU - Hoffmann, M.

AU - Okamoto, Y.

AU - Woeginger, G.J.

PY - 2006

Y1 - 2006

N2 - 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.

AB - 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.

U2 - 10.1016/j.orl.2005.01.002

DO - 10.1016/j.orl.2005.01.002

M3 - Article

VL - 34

SP - 106

EP - 110

JO - Operations Research Letters

JF - Operations Research Letters

SN - 0167-6377

IS - 1

ER -