Graph bipartitioning and spin glasses on a random network of fixed finite valence
- 21 August 1987
- journal article
- Published by IOP Publishing in Journal of Physics A: General Physics
- Vol. 20 (12) , L793-L799
- https://doi.org/10.1088/0305-4470/20/12/008
Abstract
The authors study the problem of bipartitioning a random graph of fixed finite valence using a mean-field replica-symmetric theory of an Ising ferromagnet with zero magnetisation constraint. The thermodynamics is determined by the probability distribution of an auxiliary field. The expression for the ground-state energy agrees with that proposed by Mezard and Parisi (1986) using a cavity-field method, but their expression for the fraction of crazy spins is reinterpreted.Keywords
This publication has 17 references indexed in Scilit:
- Mean-Field Theory of Randomly Frustrated Systems with Finite ConnectivityEurophysics Letters, 1987
- Bipartitioning of random graphs of fixed extensive valenceJournal of Physics A: General Physics, 1987
- Application of statistical mechanics to NP-complete problems in combinatorial optimisationJournal of Physics A: General Physics, 1986
- Optimization by Simulated AnnealingScience, 1983
- Magnetic properties of spin glasses in a new mean field theoryJournal of Physics A: General Physics, 1980
- A sequence of approximated solutions to the S-K model for spin glassesJournal of Physics A: General Physics, 1980
- The order parameter for spin glasses: a function on the interval 0-1Journal of Physics A: General Physics, 1980
- Infinite Number of Order Parameters for Spin-GlassesPhysical Review Letters, 1979
- Infinite-ranged models of spin-glassesPhysical Review B, 1978
- Solvable Model of a Spin-GlassPhysical Review Letters, 1975