کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6871072 | 1440177 | 2018 | 10 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
1.5-approximation algorithm for the 2-Convex Recoloring problem
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
We show that weighted 2-CR cannot be approximated within any ratio, unless P=NP. On the other hand, we provide an alternative definition of (unweighted) 2-CR in terms of maximum independent set of paths, which leads to a natural greedy algorithm. We prove that its approximation ratio is 32 and show that this analysis is tight. This is the first constant factor approximation algorithm for a variant of CR in general graphs. For the special case, where G is a path, the algorithm obtains a ratio of 54, an improvement over the previous best known approximation. We also consider the problem of determining whether a given graph has a convex recoloring of size k. We use the above mentioned characterization of 2-CR to show that a problem kernel of size 4k can be obtained in linear time and to design an O(|E|)+2O(klogk) time algorithm for parameterized 2-CR.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 246, 10 September 2018, Pages 2-11
Journal: Discrete Applied Mathematics - Volume 246, 10 September 2018, Pages 2-11
نویسندگان
Reuven Bar-Yehuda, Gilad Kutiel, Dror Rawitz,