Name
Abstract | ||
|---|---|---|
A fundamental result by Karger [10] states that for any λ-edge-connected graph with n nodes, independently sampling each edge with probability p = Ω(log n/λ) results in a graph that has edge connectivity Ω(λp), with high probability. This paper proves the analogous result for vertex connectivity, when sampling vertices. We show that for any k-vertex-connected graph G with n nodes, if each node is independently sampled with probability p = Ω([EQUATION]log n/k), then the subgraph induced by the sampled nodes has vertex connectivity Ω(kp2), with high probability. This bound improves upon the recent results of Censor-Hillel et al. [6], and is existentially optimal. |
Year | DOI | Venue |
|---|---|---|
2015 | 10.5555/2722129.2722262 | SODA |
DocType | ISBN | Citations |
Conference | 978-1-61197-433-1 | 3 |
PageRank | References | Authors |
0.40 | 9 | 5 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Keren Censor-Hillel | 1 | 235 | 31.73 |
| Mohsen Ghaffari | 2 | 452 | 44.89 |
| George Giakkoupis | 3 | 248 | 20.48 |
| Bernhard Haeupler | 4 | 628 | 54.00 |
| Fabian Kuhn | 5 | 4 | 1.77 |