A conjecture on the maximum cut and bisection width in random regular graphs
Authors:
- Lenka ZdeborováLZLenka Zdeborová
- Stefan BoettcherSBStefan Boettcher
- 1 February 2010
- journal article
- research article
- Published by IOP Publishing in Journal of Statistical Mechanics: Theory and Experiment
- Vol. 2010 (02) , P02020
Abstract
No abstract availableKeywords
All Related Versions
This publication has 30 references indexed in Scilit:
- Bounds on the bisection width for random d -regular graphsTheoretical Computer Science, 2007
- Bounds on the max and min bisection of random cubic and random 4-regular graphsTheoretical Computer Science, 2003
- Numerical results for ground states of mean-field spin glasses at low connectivitiesPhysical Review B, 2003
- Extremal optimization for graph partitioningPhysical Review E, 2001
- Recent directions in netlist partitioning: a surveyIntegration, 1995
- The Isoperimetric Number of Random Regular GraphsEuropean Journal of Combinatorics, 1988
- Graph bipartitioning and the Bethe spin glassJournal of Physics A: General Physics, 1987
- Graph optimisation problems and the Potts glassJournal of Physics A: General Physics, 1987
- Application of statistical mechanics to NP-complete problems in combinatorial optimisationJournal of Physics A: General Physics, 1986
- The order parameter for spin glasses: a function on the interval 0-1Journal of Physics A: General Physics, 1980