Skip to Content

The convex-hull-and-line traveling salesman problem: a solvable case

   page       BibTeX_logo.png       attach   
Vladimir G. Deineko, René van Dal, Günter Rote
Information Processing Letters 51(3), pp. 141–148
agosto 1994

We solve the special case of the Euclidean Traveling Salesman Problem where n − m cities lie on the boundary of the convex hull of all n cities, and the other m cities lie on a line segment inside this convex hull by an algorithm which needs O(mn) time and Othumb_down space.

parole chiave   Euclidean Traveling Salesman Problem, Shortest path, Well-solvable case, Polynomial time algorithm
rivista o collana
book Information Processing Letters (IPL)

The convex-hull-and-line traveling salesman problem: a solvable case
— stato
pubblicato
— tipo
articolo in rivista
chi
— autori
Vladimir G. Deineko  •  René van Dal  •  Günter Rote
dove e quando
— data di pubblicazione
agosto 1994
— rivista
Information Processing Letters
— volume n.
51
— numero
3
— pagine
141–148
— numero di pagine
8
— editore
Elsevier B.V.
URL
URL
— DOI
10.1016/0020-0190(94)00071-9
— OpenAlex
W2003687734
ISBN & ISSN
— ISSN
0020-0190
file locali
copertina  •  anteprima
APICe
— rivista o collana
Information Processing Letters