کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4960056 | 1445965 | 2017 | 10 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Polynomially solvable cases of the bipartite traveling salesman problem
ترجمه فارسی عنوان
مسائل چندمرحلهای قابل حل از فروشنده دو طرفه مسافرتی است
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
فروشنده مسافرتی، بهینه سازی ترکیبی، فروشنده دو طرفه مسافرت، املاک چهارگانه، ماتریکس کلمنسون،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
علوم کامپیوتر (عمومی)
چکیده انگلیسی
Given two sets, R and B, consisting of n cities each, in the bipartite traveling salesman problem one looks for the shortest way of visiting alternately the cities of R and B, returning to the city of origin. This problem is known to be NP-hard for arbitrary sets R and B. In this paper we provide an O(n6) algorithm to solve the bipartite traveling salesman problem if the quadrangle property holds. In particular, this algorithm can be applied to solve in O(n6) time the bipartite traveling salesman problem in the following cases: S=RâªB is a convex point set in the plane, S=RâªB is the set of vertices of a simple polygon and V=RâªB is the set of vertices of a circular graph. For this last case, we also describe another algorithm which runs in O(n2) time.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: European Journal of Operational Research - Volume 257, Issue 2, 1 March 2017, Pages 429-438
Journal: European Journal of Operational Research - Volume 257, Issue 2, 1 March 2017, Pages 429-438
نویسندگان
Alfredo GarcÃa, Javier Tejel,