The peculiar phase structure of random graph bisection

DOI10.1063/1.3043666zbMath1159.81337arXiv0808.1549OpenAlexW3101138521WikidataQ62599706 ScholiaQ62599706MaRDI QIDQ3624680

Bruno Gonçalves, Allon G. Percus, Robert Z. Sumi, Stefan Boettcher, Gabriel I. Istrate

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

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Random graphs (graph-theoretic aspects) (05C80) Graph theory (including graph drawing) in computer science (68R10) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Related Items (3)

A parametric worst-case approach to fairness in cooperative games with transferable utility ⋮ Bipartitioning of directed and mixed random graphs ⋮ Tree decompositions and social graphs

Cites Work

• 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
• Bisecting sparse random graphs
• Extremal optimization of graph partitioning at the percolation threshold

This page was built for publication: The peculiar phase structure of random graph bisection