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

Alexander K. Hartmann, Martin Weigt

Publication date: 3 March 2002

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

zbMATH Keywords

branch-and-bound algorithm; replica method; random graphs; annealed approximation; vertex-cover problem

Mathematics Subject Classification ID

05C80: Random graphs (graph-theoretic aspects)

90C57: Polyhedral combinatorics, branch-and-bound, branch-and-cut

82-02: Research exposition (monographs, survey articles) pertaining to statistical mechanics

82B41: Random walks, random surfaces, lattice animals, etc. in equilibrium statistical mechanics

Related Items

Another look at the phenomenon of phase transition, Statistical mechanics methods and phase transitions in optimization problems, Phase transition and finite-size scaling in the vertex-cover problem, Properties of atypical graphs from negative complexities, 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

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