The peculiar phase structure of random graph bisection
From MaRDI portal
Publication:3624680
DOI10.1063/1.3043666zbMath1159.81337arXiv0808.1549WikidataQ62599706 ScholiaQ62599706MaRDI QIDQ3624680
Stefan Boettcher, Allon G. Percus, Gabriel I. Istrate, Bruno Gonçalves, Robert Z. Sumi
Publication date: 30 April 2009
Published in: Journal of Mathematical Physics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/0808.1549
68Q25: Analysis of algorithms and problem complexity
05C80: Random graphs (graph-theoretic aspects)
68R10: Graph theory (including graph drawing) in computer science
68Q87: Probability in computer science (algorithm analysis, random structures, phase transitions, etc.)
Cites Work
- Unnamed Item
- Unnamed Item
- On the mixing time of a simple random walk on the super critical percolation cluster
- Nature's way of optimizing
- Monotone properties of random geometric graphs have sharp thresholds
- Application of statistical mechanics to NP-complete problems in combinatorial optimisation
- On tree census and the giant component in sparse random graphs
- Random Geometric Graphs
- Extremal optimization of graph partitioning at the percolation threshold