کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
418469 681673 2016 53 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
A 97-approximation algorithm for Graphic TSP in cubic bipartite graphs
ترجمه فارسی عنوان
یک الگوریتم تقریب ـ 97 برای TSP گرافیک در گراف‌های دوبخشی مکعب
کلمات کلیدی
الگوریتم‌های تقریبی؛ مسئله فروشنده دوره‌گرد؛ حدس بارنت ؛ بهینه سازی ترکیبی
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی

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
نویسندگان
, ,