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

Combinatorial Optimization

Research output: Contribution to journal › Article › Academic › peer-review

30 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

Cite this

@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 B.V.",

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

SN - 0167-6377

VL - 34

SP - 106

EP - 110

JO - Operations Research Letters

JF - Operations Research Letters

IS - 1

ER -

The traveling salesman problem with few inner points

Abstract

Access to Document

Fingerprint

Cite this