A random geometric graph G (n, r) is obtained by spreading n 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 r. 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 r, 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 r, any cut which separates two components of Θ (n) vertices each contains Ω (n2 r3) edges with high probability. We also present a simple algorithm that, again with high probability, computes one such cut of size O (n2 r3). 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 β n vertices each. © 2009 Elsevier B.V. All rights reserved.
Balanced cut approximation in random geometric graphs / Josep, Diaz; Grandoni, Fabrizio; MARCHETTI SPACCAMELA, Alberto. - In: THEORETICAL COMPUTER SCIENCE. - ISSN 0304-3975. - 410:27-29(2009), pp. 2725-2731. [10.1016/j.tcs.2009.03.037]
Balanced cut approximation in random geometric graphs
GRANDONI, FABRIZIO;MARCHETTI SPACCAMELA, Alberto
2009
Abstract
A random geometric graph G (n, r) is obtained by spreading n 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 r. 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 r, 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 r, any cut which separates two components of Θ (n) vertices each contains Ω (n2 r3) edges with high probability. We also present a simple algorithm that, again with high probability, computes one such cut of size O (n2 r3). 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 β n vertices each. © 2009 Elsevier B.V. All rights reserved.File | Dimensione | Formato | |
---|---|---|---|
VE_2009_11573-360736.pdf
solo gestori archivio
Tipologia:
Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza:
Tutti i diritti riservati (All rights reserved)
Dimensione
504.36 kB
Formato
Adobe PDF
|
504.36 kB | Adobe PDF | Contatta l'autore |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.