کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
420721 | 683972 | 2009 | 12 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Highly connected random geometric graphs
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: Highly connected random geometric graphs Highly connected random geometric graphs](/preview/png/420721.png)
چکیده انگلیسی
Let PP be a Poisson process of intensity 1 in a square SnSn of area nn. We construct a random geometric graph Gn,kGn,k by joining each point of PP to its kk nearest neighbours. For many applications it is desirable that Gn,kGn,k is highly connected, that is, it remains connected even after the removal of a small number of its vertices. In this paper we relate the study of the ss-connectivity of Gn,kGn,k to our previous work on the connectivity of Gn,kGn,k. Roughly speaking, we show that for s=o(logn)s=o(logn), the threshold (in kk) for ss-connectivity is asymptotically the same as that for connectivity, so that, as we increase kk, Gn,kGn,k becomes ss-connected very shortly after it becomes connected.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 157, Issue 2, 28 January 2009, Pages 309–320
Journal: Discrete Applied Mathematics - Volume 157, Issue 2, 28 January 2009, Pages 309–320
نویسندگان
Paul Balister, Béla Bollobás, Amites Sarkar, Mark Walters,