کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
480241 | 1446067 | 2012 | 13 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
The x-and-y-axes travelling salesman problem
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
علوم کامپیوتر (عمومی)
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: The x-and-y-axes travelling salesman problem The x-and-y-axes travelling salesman problem](/preview/png/480241.png)
چکیده انگلیسی
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.
► A special solvable case of the travelling salesman problem (TSP) is considered.
► All cities in this TSP are situated on the x-and-y-axes of the Euclidean plane.
► The problem remained open since 1980.
► The running time of our algorithm is quadratic in the number of cities.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: European Journal of Operational Research - Volume 223, Issue 2, 1 December 2012, Pages 333–345
Journal: European Journal of Operational Research - Volume 223, Issue 2, 1 December 2012, Pages 333–345
نویسندگان
Eranda Çela, Vladimir Deineko, Gerhard J. Woeginger,