Name
Abstract | ||
|---|---|---|
Consider partitions of the vertex set of a graph G into two sets with sizes differing by at most 1: the bisection width of G is the minimum over all such partitions of the number of "cross edges" between the parts. We are interested in sparse random graphs G(n,c/n) with edge probability c/n. We show that, if c > 1n 4, then the bisection width is Omega (n) with high probability; while if c < 1n 4, then it is equal to 0 with high probability. There are corresponding threshold results for partitioning into any fixed number of parts. (C) 2001 John Wiley & Sons, Inc. |
Year | DOI | Venue |
|---|---|---|
2001 | 3.0.CO;2-1" target="_self" class="small-link-text"10.1002/1098-2418(200101)18:13.0.CO;2-1 | Random Struct. Algorithms |
Keywords | Field | DocType |
random graph | Random regular graph,Graph,Discrete mathematics,Combinatorics,Random graph,Bisection,Vertex (geometry),struct,Mathematics | Journal |
Volume | Issue | ISSN |
18 | 1 | 1042-9832 |
Citations | PageRank | References |
7 | 0.93 | 4 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Malwina J. Luczak | 1 | 95 | 10.93 |
| Colin McDiarmid | 2 | 1071 | 167.05 |