کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6876262 | 689734 | 2013 | 19 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
The cover times of random walks on random uniform hypergraphs
ترجمه فارسی عنوان
زمان پوشش های پیاده روی تصادفی بر روی هیپوگرافی های تصادفی
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
پیاده روی تصادفی، هیپوگرافی، زمان پوشش نمودار تصادفی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
In this paper we give an expression for C(H) which is tractable for many classes of hypergraphs, and calculate C(H) and I(H) exactly for random r-regular, s-uniform hypergraphs. We find that for such hypergraphs, whp, C(H)/I(H)â¼s(râ1)/r, if rs=O((loglogn)1âϵ). For random r-regular, s-uniform multi-hypergraphs, constant râ¥2, and 3â¤sâ¤O(nϵ), we also prove that, whp, I(H)=O((n/s)logn), i.e. the inform time decreases directly with the edge size s.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 509, 21 October 2013, Pages 51-69
Journal: Theoretical Computer Science - Volume 509, 21 October 2013, Pages 51-69
نویسندگان
Colin Cooper, Alan Frieze, Tomasz Radzik,