Statistical mechanics perspective on the phase transition in vertex covering finite-connectivity random graphs
Alexander K. HartmannMartin WeigtPublished in: CoRR (2000)
Keyphrases
- random graphs
- phase transition
- statistical mechanics
- hamiltonian cycle
- average degree
- attributed graphs
- information theory
- constraint satisfaction
- undirected graph
- hard problems
- np complete
- satisfiability problem
- random instances
- connected components
- randomly generated
- np complete problems
- graph coloring
- random constraint satisfaction problems
- graph theoretic
- free energy
- information theoretic
- cellular automata
- sat problem
- directed graph
- heuristic search