Random Instances of a Graph Coloring Problem Are Hard
Ramarathnam VenkatesanLeonid A. LevinPublished in: STOC (1988)
Keyphrases
- random instances
- phase transition
- graph coloring
- constraint satisfaction problems
- np complete problems
- randomly generated
- lower bound
- hard problems
- random constraint satisfaction problems
- constraint satisfaction
- combinatorial problems
- search problems
- sat instances
- satisfiability problem
- np complete
- pattern databases
- random graphs
- sat problem