کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6894567 | 1445926 | 2018 | 26 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Fixed-parameter algorithms for rectilinear Steiner tree and rectilinear traveling salesman problem in the plane
ترجمه فارسی عنوان
الگوریتم های پارامتر ثابت برای درخت مستطیلی استینر و مشکلات فروشندگان خطی در هواپیما
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
علوم کامپیوتر (عمومی)
چکیده انگلیسی
Given a set P of n points with their pairwise distances, the traveling salesman problem (TSP) asks for a shortest tour that visits each point exactly once. A TSP instance is rectilinear when the points lie in the plane and the distance considered between two points is the l1 distance. In this paper, a fixed-parameter algorithm for the Rectilinear TSP is presented and relies on techniques for solving TSP on bounded-treewidth graphs. It proves that the problem can be solved in O(nh7h) where hâ¯â¤â¯n denotes the number of horizontal lines containing the points of P. The same technique can be directly applied to the problem of finding a shortest rectilinear Steiner tree that interconnects the points of P providing a O(nh5h) time complexity. Both bounds improve over the best time bounds known for these problems.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: European Journal of Operational Research - Volume 270, Issue 2, 16 October 2018, Pages 419-429
Journal: European Journal of Operational Research - Volume 270, Issue 2, 16 October 2018, Pages 419-429
نویسندگان
Hadrien Cambazard, Nicolas Catusse,