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

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

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

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

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

ترجمه کلمات کلیدی
حداقل مجموعه غالب مستقل؛ الگوریتم تصاعدی؛ الگوریتم های دقیق - الگوریتم های تقریبی
کلمات کلیدی انگلیسی
min independent dominating set; Exponential algorithms; Exact algorithms; Approximation algorithms
پیش نمایش مقاله
پیش نمایش مقاله   الگوریتم های سریع برای حداقل مجموعه غالب مستقل  .

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

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.