کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6871335 | 1440184 | 2018 | 23 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Improved approximation algorithms for weighted 2-path partitions
ترجمه فارسی عنوان
الگوریتم های تقریبی بهبود یافته برای پارتیشن های وزن دو طرفه
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
تقسیم بندی نمودار، بسته بندی گراف، عامل گراف، الگوریتم های تقریبی،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
Combining this algorithm with a previously known approximation algorithm for the 3-Set Packing problem, we obtain a .6-approximation algorithm for the problem of partitioning a {0,1}-edge-weighted graph into k vertex disjoint triangles of maximum total weight. The best known approximation algorithm for general weights is due to Chen and Tanahashi (2009) and achieves an approximation ratio of .5257.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 239, 20 April 2018, Pages 15-37
Journal: Discrete Applied Mathematics - Volume 239, 20 April 2018, Pages 15-37
نویسندگان
Amotz Bar-Noy, David Peleg, George Rabanca, Ivo Vigan,