Approximation for vertex cover in β-conflict graphs.
Dongjing MiaoZhipeng CaiWeitian TongJianzhong LiPublished in: J. Comb. Optim. (2017)
Keyphrases
- vertex cover
- approximation algorithms
- planar graphs
- polynomial time approximation
- undirected graph
- approximation guarantees
- np hard
- approximation ratio
- special case
- worst case
- graph theory
- minimum cost
- partial order
- precedence constraints
- error bounds
- directed graph
- optimal solution
- closed form
- minimum spanning tree
- graph cuts
- scheduling problem