Diameter, connectivity, and phase transition of the uniform random intersection graph.
Katarzyna RybarczykPublished in: Discret. Math. (2011)
Keyphrases
- phase transition
- average degree
- uniform random
- constraint satisfaction
- random graphs
- hamiltonian cycle
- satisfiability problem
- randomly generated
- np complete
- graph coloring
- random walk
- connected components
- random instances
- hard problems
- small world networks
- np complete problems
- random constraint satisfaction problems
- sat problem
- special case
- cellular automata
- network size
- constraint satisfaction problems
- upper bound
- np hard