Name
Abstract | ||
|---|---|---|
In the planted bisection model a random graph G(n, p(+ ), p(-)) with n vertices is created by partitioning the vertices randomly into two classes of equal size (up to +/- 1). Any two vertices that belong to the same class are linked by an edge with probability p(+) and any two that belong to different classes with probability p(-) < p(+) independently. The planted bisection model has been used extensively to benchmark graph partitioning algorithms. If p(+/-) = 2d(+/-)/n for numbers 0 <= d(-) < d(+) that remain fixed as n -> infinity, then w. h. p. the "planted" bisection (the one used to construct the graph) will not be a minimum bisection. In this paper we derive an asymptotic formula for the minimum bisection width under the assumption that d(+) - d(-) > c root d(+)lnd(+) for a certain constant c > 0. |
Year | DOI | Venue |
|---|---|---|
2015 | 10.4086/toc.2017.v013a008 | THEORY OF COMPUTING |
Keywords | DocType | Volume |
random graphs,minimum bisection,planted bisection,belief propagation | Journal | 13 |
Issue | ISSN | Citations |
1 | 1557-2862 | 1 |
PageRank | References | Authors |
0.36 | 13 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Amin Coja-Oghlan | 1 | 543 | 47.25 |
| Oliver Cooley | 2 | 3 | 2.13 |
| Mihyun Kang | 3 | 163 | 29.18 |
| kathrin skubch | 4 | 2 | 1.41 |