Diaz, Josep and Grandoni, Fabrizio and Marchetti-Spaccamela, Alberto (2009) Balanced cut approximation in random geometric graphs. Theoretical Computer Science, 410 (27-29). pp. 2725-2731. ISSN 0304-3975
Full text not available from this repository.Abstract
A random geometric graph G(n,r)G(n,r) is obtained by spreading nn points uniformly at random in a unit square, and by associating a vertex to each point and an edge to each pair of points at Euclidian distance at most rr. Such graphs are extensively used to model wireless ad-hoc networks, and in particular sensor networks. It is well known that, over a critical value of rr, the graph is connected with high probability. In this paper we study the robustness of the connectivity of random geometric graphs in the supercritical phase, under deletion of edges. In particular, we show that, for a sufficiently large rr, any cut which separates two components of Θ(n)Θ(n) vertices each contains Ω(n2r3)Ω(n2r3) edges with high probability. We also present a simple algorithm that, again with high probability, computes one such cut of size O(n2r3)O(n2r3). From these two results we derive a constant expected approximation algorithm for the ββ-balanced cut problem on random geometric graphs: find an edge cut of minimum size whose two sides contain at least View the MathML sourceβn vertices each.
| Item Type: | Scientific journal article, Newspaper article or Magazine article |
|---|---|
| Uncontrolled Keywords: | Ad-hoc networks; Sensor networks; Random geometric graphs; Balanced cut; Approximation algorithms |
| Subjects: | Computer sciences |
| Depositing User: | Fabrizio Grandoni |
| Date Deposited: | 14 Mar 2014 08:59 |
| Last Modified: | 23 May 2016 14:45 |
| URI: | http://repository.supsi.ch/id/eprint/4499 |
Actions (login required)
 |
View Item |