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