کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
437607 690164 2015 7 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Two greedy consequences for maximum induced matchings
ترجمه فارسی عنوان
دو عواقب حریص برای حداکثر ملاقات القا شده
کلمات کلیدی
مطابقت القاء شده، الگوریتم حریص، الگوریتم تقریبی، شاخص رنگی قوی، نمودار بروز
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی

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