کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
436153 | 689974 | 2015 | 17 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Inapproximability of dominating set on power law graphs
ترجمه فارسی عنوان
غیر قابل تصور بودن تسلط بر نمودارهای قانون قدرت
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
الگوریتم های تقریبی، غیر قابل پیش بینی بودن نمودارهای قدرت قانون، بهینه سازی ترکیبی، مجموعه غالب
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
We prove the first logarithmic lower bounds for the approximability of the Minimum Dominating Set problem for the case of connected (α,β)(α,β)-power law graphs for α being a size parameter and β the power law exponent. We give also a best up to now upper approximation bound for this problem in the case of the parameters β>2β>2. We develop also a new functional method for proving lower approximation bounds and display a sharp approximation phase transition area between approximability and inapproximability of the underlying problems. Our results depend on a method which could be also of independent interest.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 562, 11 January 2015, Pages 436–452
Journal: Theoretical Computer Science - Volume 562, 11 January 2015, Pages 436–452
نویسندگان
Mikael Gast, Mathias Hauptmann, Marek Karpinski,