کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
437607 | 690164 | 2015 | 7 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Two greedy consequences for maximum induced matchings
ترجمه فارسی عنوان
دو عواقب حریص برای حداکثر ملاقات القا شده
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
مطابقت القاء شده، الگوریتم حریص، الگوریتم تقریبی، شاخص رنگی قوی، نمودار بروز
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
We prove that, for every integer d with d≥3d≥3, there is an approximation algorithm for the maximum induced matching problem restricted to {C3,C5}{C3,C5}-free d -regular graphs with performance ratio 0.7083¯d+0.425, which answers a question posed by Dabrowski et al. (Theoret. Comput. Sci. 478 (2013) 33–40). Furthermore, we show that every graph with m edges that is k-degenerate and of maximum degree at most d with k
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 602, 18 October 2015, Pages 32–38
Journal: Theoretical Computer Science - Volume 602, 18 October 2015, Pages 32–38
نویسندگان
Dieter Rautenbach,