کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
418469 | 681673 | 2016 | 53 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
A 97-approximation algorithm for Graphic TSP in cubic bipartite graphs
ترجمه فارسی عنوان
یک الگوریتم تقریب ـ 97 برای TSP گرافیک در گرافهای دوبخشی مکعب
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
الگوریتمهای تقریبی؛ مسئله فروشنده دورهگرد؛ حدس بارنت ؛ بهینه سازی ترکیبی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
We prove new results for approximating the Graphic TSP. Specifically, we provide a polynomial-time 97-approximation algorithm for cubic bipartite graphs and a (97+121(k−2))-approximation algorithm for kk-regular bipartite graphs, both of which are improved approximation factors compared to previous results. Our approach involves finding a cycle cover with relatively few cycles, which we are able to do by leveraging the fact that all cycles in bipartite graphs are of even length along with our knowledge of the structure of cubic graphs.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 209, 20 August 2016, Pages 164–216
Journal: Discrete Applied Mathematics - Volume 209, 20 August 2016, Pages 164–216
نویسندگان
Jeremy A. Karp, R. Ravi,