کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4952477 | 1442038 | 2016 | 15 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Minimum vertex cover in generalized random graphs with power law degree distribution
ترجمه فارسی عنوان
حداقل پوشش گردشی در نمودارهای تصادفی تعمیم یافته با توزیع درجه حقوقی قدرت
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
In this paper we study the approximability of the minimum vertex cover problem in power law graphs. In particular, we investigate the behavior of a standard 2-approximation algorithm together with a simple pre-processing step when the input is a random sample from a generalized random graph model with power law degree distribution. More precisely, if the probability of a vertex of degree i to be present in the graph is ciâβ, where β>2 and c is a normalizing constant, the expected approximation ratio is 1+ζ(β)â1Liβ(eâÏ(β)), where ζ(β) is the Riemann Zeta function of β, Li(β) is the polylogarithmic special function of β and Ï(β)=Liβâ2(1e)ζ(βâ1).
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 647, 27 September 2016, Pages 101-111
Journal: Theoretical Computer Science - Volume 647, 27 September 2016, Pages 101-111
نویسندگان
André L. Vignatti, Murilo V.G. da Silva,