Improved approximation algorithms for the vertex cover problem in graphs and hypergraphs.
Eran HalperinPublished in: SODA (2000)
Keyphrases
- vertex cover
- approximation algorithms
- planar graphs
- undirected graph
- np hard
- special case
- graph theory
- minimum cost
- worst case
- approximation ratio
- polynomial time approximation
- partial order
- spanning tree
- approximation guarantees
- primal dual
- precedence constraints
- directed graph
- weighted graph
- log likelihood
- dynamic programming
- optimality criterion
- computational complexity