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

Onderzoeksoutput: Bijdrage aan tijdschrift › Tijdschriftartikel › Academic › peer review

30 Citaten (Scopus)

1 Downloads (Pure)

Samenvatting

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.

Originele taal-2	Engels
Pagina's (van-tot)	106-110
Tijdschrift	Operations Research Letters
Volume	34
Nummer van het tijdschrift	1
DOI's	https://doi.org/10.1016/j.orl.2005.01.002
Status	Gepubliceerd - 2006

Toegang tot document

10.1016/j.orl.2005.01.002

Citeer dit

@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

Samenvatting

Toegang tot document

Vingerafdruk

Citeer dit