|
|||||
|
|
The x-and-y-axes travelling salesman problem |
|
| Authors: | Eranda Çela Vladimir Deineko Gerhard J Woeginger |
| Institution: | 1. Institut für Optimierung und Diskrete Mathematik, TU Graz, Steyrergasse 30, A-8010 Graz, Austria;2. Warwick Business School, Coventry CV4 7AL, United Kingdom;3. Department of Mathematics and Computer Science, TU Eindhoven, P.O. Box 513, 5600 MB Eindhoven, Netherlands |
| Abstract: | 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. |
| Keywords: | Combinatorial optimization Polynomial-time algorithm Computational complexity Euclidean travelling salesman problem |
| 本文献已被 ScienceDirect 等数据库收录！ | |