Approximability of the Vertex Cover Problem in Power Law Graphs
Mikael GastMathias HauptmannPublished in: CoRR (2012)
Keyphrases
- power law
- vertex cover
- approximation algorithms
- small world
- polynomial time approximation
- planar graphs
- real world graphs
- np hard
- degree distribution
- special case
- random graphs
- undirected graph
- worst case
- scale free
- partial order
- minimum cost
- power law distribution
- approximation ratio
- clustering coefficient
- error bounds
- lower bound
- state space
- approximation guarantees
- graph theory