دانلود مقاله ISI انگلیسی شماره 79033
عنوان فارسی مقاله

الگوریتم های سریع برای حداقل مجموعه غالب مستقل .

کد مقاله سال انتشار مقاله انگلیسی ترجمه فارسی تعداد کلمات
79033 2013 15 صفحه PDF سفارش دهید محاسبه نشده
خرید مقاله
پس از پرداخت، فوراً می توانید مقاله را دانلود فرمایید.
عنوان انگلیسی
Fast algorithms for min independent dominating set ☆
منبع

Publisher : Elsevier - Science Direct (الزویر - ساینس دایرکت)

Journal : Discrete Applied Mathematics, Volume 161, Issues 4–5, March 2013, Pages 558–572

کلمات کلیدی
حداقل مجموعه غالب مستقل؛ الگوریتم تصاعدی؛ الگوریتم های دقیق - الگوریتم های تقریبی
پیش نمایش مقاله
پیش نمایش مقاله  الگوریتم های سریع برای حداقل مجموعه غالب مستقل  .

چکیده انگلیسی

We first devise a branching algorithm that computes a minimum independent dominating set with running time O∗(1.3351n)=O∗(20.417n)O∗(1.3351n)=O∗(20.417n) and polynomial space. This improves upon the best state of the art algorithms for this problem. We then study approximation of the problem by moderately exponential time algorithms and show that it can be approximated within ratio 1+ϵ1+ϵ, for any ϵ>0ϵ>0, in a time smaller than the one of exact computation and exponentially decreasing with ϵϵ. We also propose approximation algorithms with better running times for ratios greater than 3 in general graphs and give improved moderately exponential time approximation results in triangle-free and bipartite graphs. These latter results are based upon a new bound on the number of maximal independent sets of a given size in these graphs, which is a result interesting per se.

خرید مقاله
پس از پرداخت، فوراً می توانید مقاله را دانلود فرمایید.