Phase transition and finite-size scaling in the vertex-cover problem.
Alexander K. HartmannWolfgang BarthelMartin WeigtPublished in: Comput. Phys. Commun. (2005)
Keyphrases
- phase transition
- vertex cover
- constraint satisfaction
- approximation algorithms
- satisfiability problem
- randomly generated
- np complete
- sat problem
- partial order
- cellular automata
- random constraint satisfaction problems
- precedence constraints
- planar graphs
- random instances
- random walk
- dynamic programming
- computational complexity