The x-and-y-axes travelling salesman problem

E. Çela, V.G. Deineko, G.J. Woeginger

Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

5 Citaten (Scopus)


The x-and-y-axes travelling salesman problem forms a special case of the Euclidean TSP, where all cities are situated on the x-axis and on the y-axis of an orthogonal coordinate system of the Euclidean plane. By carefully analyzing the underlying combinatorial and geometric structures, we show that this problem can be solved in polynomial time. The running time of the resulting algorithm is quadratic in the number of cities.
Originele taal-2Engels
Pagina's (van-tot)333-345
TijdschriftEuropean Journal of Operational Research
Nummer van het tijdschrift2
StatusGepubliceerd - 2012


Duik in de onderzoeksthema's van 'The x-and-y-axes travelling salesman problem'. Samen vormen ze een unieke vingerafdruk.

Citeer dit