Vertex Cover Approximations on Random Graphs.
Eyjolfur Ingi AsgeirssonClifford SteinPublished in: WEA (2007)
Keyphrases
- vertex cover
- random graphs
- approximation algorithms
- graph theoretic
- undirected graph
- partial order
- planar graphs
- precedence constraints
- phase transition
- small world
- optimality criterion
- closed form
- scheduling problem
- special case
- np complete
- power law
- log likelihood
- image segmentation
- minimum cost
- graph theory
- polynomial time approximation
- complex networks