Inapproximability of Vertex Cover and Independent Set in Bounded Degree Graphs.
Per AustrinSubhash KhotMuli SafraPublished in: Theory Comput. (2011)
Keyphrases
- independent set
- vertex cover
- approximation algorithms
- bounded degree
- maximum independent set
- np hard
- graph theoretic
- special case
- maximum weight
- worst case
- partial order
- minimum cost
- planar graphs
- undirected graph
- precedence constraints
- bounded treewidth
- relational databases
- polynomial time approximation
- graph theory