Inapproximability of Vertex Cover and Independent Set in Bounded Degree Graphs.
Per AustrinSubhash KhotMuli SafraPublished in: Computational Complexity Conference (2009)
Keyphrases
- independent set
- vertex cover
- approximation algorithms
- bounded degree
- np hard
- maximum independent set
- worst case
- special case
- maximum weight
- graph theoretic
- partial order
- undirected graph
- planar graphs
- precedence constraints
- optimality criterion
- polynomial time approximation
- minimum cost
- log likelihood
- bounded treewidth
- approximation guarantees
- directed graph