Open Access. Powered by Scholars. Published by Universities.®
Articles 1 - 4 of 4
Full-Text Articles in Entire DC Network
Sentry Selection In Wireless Networks, Paul Balister, Béla Bollobás, Amites Sarkar, Mark Walters
Sentry Selection In Wireless Networks, Paul Balister, Béla Bollobás, Amites Sarkar, Mark Walters
Mathematics Faculty Publications
Let P be a Poisson process of intensity one in the infinite plane R2. We surround each point x of P by the open disc of radius r centred at x. Now let Sn be a fixed disc of area n, and let Cr(Sn) be the set of discs which intersect Sn. Write Erk for the event that Cr(Sn) is a k-cover of Sn, and Frk for the event that Cr(Sn) …
Highly Connected Random Geometric Graphs, Paul Balister, Béla Bollobás, Amites Sarkar, Mark Walters
Highly Connected Random Geometric Graphs, Paul Balister, Béla Bollobás, Amites Sarkar, Mark Walters
Mathematics Faculty Publications
Let P be a Poisson process of intensity 1 in a square Sn of area n. We construct a random geometric graph Gn,k by joining each point of P to its k nearest neighbours. For many applications it is desirable that Gn,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 s-connectivity of Gn,k to our previous work on the connectivity of Gn,k. Roughly speaking, we show that for s=o(logn), the threshold (in k) for …
A Critical Constant For The K Nearest-Neighbour Model, Paul Balister, Béla Bollobás, Amites Sarkar, Mark Walters
A Critical Constant For The K Nearest-Neighbour Model, Paul Balister, Béla Bollobás, Amites Sarkar, Mark Walters
Mathematics Faculty Publications
Let P be a Poisson process of intensity 1 in a square Sn of area n. For a fixed integer k, join every point of P to its k nearest neighbours, creating an undirected random geometric graph Gn,k. We prove that there exists a critical constant ccrit such that, for c‹ccrit, Gn,⌊clogn⌋ is disconnected with probability tending to 1 as n →∞ and, for c‹ccrit, Gn,⌊clogn⌋ is connected with probability tending to 1 as n →∞. This answers a question …
Connectivity Of Random K-Nearest-Neighbor Graphs, Paul Balister, Béla Bollobás, Amites Sarkar, Mark Walters
Connectivity Of Random K-Nearest-Neighbor Graphs, Paul Balister, Béla Bollobás, Amites Sarkar, Mark Walters
Mathematics Faculty Publications
Let P be a Poisson process of intensity one in a square Sn of area n. We construct a random geometric graph Gn,k by joining each point of Pto its k ≡ k(n) nearest neighbours. Recently, Xue and Kumar proved that if k ≤ 0.074logn then the probability that Gn,k is connected tends to 0 as n → ∞ while, if k ≥ 5.1774logn, then the probability that Gn,k is connected tends to 1 as n → ∞. They conjectured that the …