A phase transition for avoiding a giant component.
Tom BohmanJeong Han KimPublished in: Random Struct. Algorithms (2006)
Keyphrases
- phase transition
- constraint satisfaction
- np complete
- satisfiability problem
- randomly generated
- hard problems
- combinatorial problems
- random constraint satisfaction problems
- average degree
- hamiltonian cycle
- np complete problems
- graph coloring
- random instances
- relational learning
- cellular automata
- sat problem
- deep structure
- magnetic field
- connected components
- sat instances
- heuristic search
- upper bound
- lower bound
- objective function