Statistical mechanics perspective on the phase transition in vertex covering of finite-connectivity random graphs

DOI10.1016/S0304-3975(01)00163-3zbMath1026.82014WikidataQ58001608 ScholiaQ58001608MaRDI QIDQ5958808

Martin Weigt, Alexander K. Hartmann

Publication date: 3 March 2002

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

branch-and-bound algorithmreplica methodrandom graphsannealed approximationvertex-cover problem

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Research exposition (monographs, survey articles) pertaining to statistical mechanics (82-02) Random walks, random surfaces, lattice animals, etc. in equilibrium statistical mechanics (82B41)

Related Items

Properties of atypical graphs from negative complexities, Probing the space of toric quiver theories, Analysis of an iterated local search algorithm for vertex cover in sparse random graphs, Another look at the phenomenon of phase transition, Phase transition and finite-size scaling in the vertex-cover problem, Restarts and exponential acceleration of the Davis-Putnam-Loveland-Logemann algorithm: A large deviation analysis of the generalized unit clause heuristic for random 3-SAT, Statistical mechanics methods and phase transitions in optimization problems

Uses Software

• LEDA

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the independence number of random graphs
• A lower bound on the independence number of a graph
• Phase transitions and the search problem
• Independent sets in random sparse graphs
• Cliques in random graphs
• Finding a Maximum Independent Set
• Optimization problems and replica symmetry breaking in finite connectivity spin glasses
• Phase Transition in the Number Partitioning Problem
• Determining computational complexity from characteristic ‘phase transitions’
• Branch-and-Bound Methods: A Survey