PTAS for the minimum k-path connected vertex cover problem in unit disk graphs.
Xianliang LiuHongliang LuWei WangWeili WuPublished in: J. Glob. Optim. (2013)
Keyphrases
- vertex cover
- approximation algorithms
- minimum cost
- spanning tree
- polynomial time approximation
- undirected graph
- constant factor
- np hard
- planar graphs
- special case
- worst case
- approximation guarantees
- minimum spanning tree
- error bounds
- connected components
- graph theory
- weighted graph
- approximation ratio
- directed graph
- precedence constraints
- partial order
- shortest path
- lower bound