Journal article

### Bisecting sparse random graphs.

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 Gn,c/n with edge probability c/n. We show that, if c > ln 4, then the bisection width is Ω(n) with high probability; while if c < ln 4, then it is equal to 0 with high probability. There are corresponding threshold results for partiti...

Publication status:
Published

### Authors

Journal:
Random Struct. Algorithms
Volume:
18
Issue:
1
Pages:
31-38
Publication date:
2001-01-01
DOI:
ISSN:
1042-9832
Source identifiers:
102309
Language:
English
Pubs id:
pubs:102309
UUID:
uuid:b34475ea-02fa-4825-ac49-10882880c096
Local pid:
pubs:102309
Deposit date:
2012-12-19