کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
421116 | 684142 | 2015 | 9 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Parameterized clique on inhomogeneous random graphs
ترجمه فارسی عنوان
کلیدهای پارامتریک بر روی نمودارهای تصادفی غیرمجاز
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
کلک، شبکه مقیاس آزاد، نمودار قانون قدرت گراف تصادفی غیرمنتظره
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
Finding cliques in graphs is a classical problem which is in general NP-hard and parameterized intractable. In typical applications like social networks or biological networks, however, the considered graphs are scale-free, i.e., their degree sequence follows a power law. Their specific structure can be algorithmically exploited and makes it possible to solve clique much more efficiently. We prove that on inhomogeneous random graphs with nn nodes and power law exponent ββ, cliques of size kk can be found in time O(n)O(n) for β≥3β≥3 and in time O(nek4)O(nek4) for 2<β<32<β<3.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 184, 31 March 2015, Pages 130–138
Journal: Discrete Applied Mathematics - Volume 184, 31 March 2015, Pages 130–138
نویسندگان
Tobias Friedrich, Anton Krohmer,