کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6876245 | 689735 | 2014 | 23 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Constructions of independent sets in random intersection graphs
ترجمه فارسی عنوان
ساختار مجموعه های مستقل در نمودار تقاطع تصادفی
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
نمودار تقاطع تصادفی مستقل (پایدار) مجموعه، الگوریتم حریص،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
This paper concerns constructing independent sets in a random intersection graph. We concentrate on two cases of the model: a binomial and a uniform random intersection graph. For both models we analyse two greedy algorithms and prove that they find asymptotically almost optimal independent sets. We provide detailed analysis of the presented algorithms and give tight bounds on the independence number for the studied models. Moreover we determine the range of parameters for which greedy algorithms give better results for a random intersection graph than this is in the case of an ErdÅs-Rényi random graph G(n,pË).
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 524, 6 March 2014, Pages 103-125
Journal: Theoretical Computer Science - Volume 524, 6 March 2014, Pages 103-125
نویسندگان
Katarzyna Rybarczyk,