An Empirical Study of MAX-2-SAT Phase Transitions.
Haiou ShenHantao ZhangPublished in: Electron. Notes Discret. Math. (2003)
Keyphrases
- phase transition
- max sat
- sat problem
- satisfiability problem
- constraint satisfaction
- graph coloring
- weighted max sat
- np complete problems
- np complete
- stochastic local search
- randomly generated
- combinatorial problems
- boolean satisfiability
- hard problems
- propositional satisfiability
- sat solvers
- random sat
- random constraint satisfaction problems
- lower bound
- maximum satisfiability
- max sat solver
- branch and bound algorithm
- cnf formula
- davis putnam
- branch and bound
- sat instances
- random instances
- cellular automata
- tabu search
- conjunctive normal form
- search strategies