Graph bipartitioning and statistical mechanics

DOI10.1088/0305-4470/20/1/001zbMATH Open0621.05027OpenAlexW2038996833MaRDI QIDQ3757938FDOQ3757938

Nicolas Sourlas, David Sherrington, Jayanth R. Banavar

Publication date: 1987

Published in: Journal of Physics A: Mathematical and General (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1088/0305-4470/20/1/001

Recommendations

• Bipartitioning of random graphs of fixed extensive valence
• Application of statistical mechanics to NP-complete problems in combinatorial optimisation
• q-partitioning of graphs with finite coordination number
• Bipartitioning of directed and mixed random graphs
• The Metropolis algorithm for graph bisection

zbMATH Keywords

random graphbipartitioning

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Classical equilibrium statistical mechanics (general) (82B05) Statistical thermodynamics (82B30)

Cited In (8)

• Statistical mechanics methods and phase transitions in optimization problems
• Graph weights arising from statistical mechanics
• A numerical study of sparse random matrices
• Bipartitioning of random graphs of fixed extensive valence
• Neutrality in fitness landscapes.
• On Dependency Graphs and the Lattice Gas
• q-partitioning of graphs with finite coordination number
• Bipartitioning of directed and mixed random graphs

This page was built for publication: Graph bipartitioning and statistical mechanics

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3757938)