The x-and-y-axes travelling salesman problem
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.
If you experience problems downloading a file, check if you have the proper application to view it first. In case of further problems read the IDEAS help page. Note that these files are not on the IDEAS site. Please be patient as the files may be large.
As the access to this document is restricted, you may want to look for a different version under "Related research" (further below) or search for a different version of it.
References listed on IDEAS
Please report citation or reference errors to , or , if you are the registered author of the cited work, log in to your RePEc Author Service profile, click on "citations" and make appropriate adjustments.:
- van der Veen, Jack A. A. & Sierksma, Gerard & van Dal, Rene, 1991. "Pyramidal tours and the traveling salesman problem," European Journal of Operational Research, Elsevier, vol. 52(1), pages 90-102, May.
- van Dal, Rene & van der Veen, Jack A. A. & Sierksma, Gerard, 1993. "Small and large TSP: Two polynomially solvable cases of the traveling salesman problem," European Journal of Operational Research, Elsevier, vol. 69(1), pages 107-120, August.
- Özpeynirci, Özgür & Köksalan, Murat, 2009. "Multiobjective traveling salesperson problem on Halin graphs," European Journal of Operational Research, Elsevier, vol. 196(1), pages 155-161, July.
- Oda, Yoshiaki, 2002. "An asymmetric analog of van der Veen conditions and the traveling salesman problem (II)," European Journal of Operational Research, Elsevier, vol. 138(1), pages 43-62, April.
- Bagchi, Tapan P. & Gupta, Jatinder N.D. & Sriskandarajah, Chelliah, 2006. "A review of TSP based approaches for flowshop scheduling," European Journal of Operational Research, Elsevier, vol. 169(3), pages 816-854, March.
When requesting a correction, please mention this item's handle: RePEc:eee:ejores:v:223:y:2012:i:2:p:333-345. See general information about how to correct material in RePEc.
For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Zhang, Lei)
If references are entirely missing, you can add them using this form.