کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
6871335 1440184 2018 23 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Improved approximation algorithms for weighted 2-path partitions
ترجمه فارسی عنوان
الگوریتم های تقریبی بهبود یافته برای پارتیشن های وزن دو طرفه
کلمات کلیدی
تقسیم بندی نمودار، بسته بندی گراف، عامل گراف، الگوریتم های تقریبی،
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی
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
نویسندگان
, , , ,