Shifting the Phase Transition Threshold for Random Graphs and 2-SAT using Degree Constraints.
Sergey DovgalVlady RavelomananaPublished in: CoRR (2017)
Keyphrases
- phase transition
- random graphs
- constraint satisfaction
- combinatorial problems
- satisfiability problem
- sat problem
- np complete
- randomly generated
- graph coloring
- stochastic local search
- random instances
- np complete problems
- hard problems
- cellular automata
- boolean satisfiability
- constraint satisfaction problems
- constraint programming
- sat solvers
- heuristic search