PTAS for minimum k-path vertex cover in ball graph.
Zhao ZhangXiaoting LiYishuo ShiHongmei NieYuqing ZhuPublished in: Inf. Process. Lett. (2017)
Keyphrases
- vertex cover
- approximation algorithms
- minimum cost
- constant factor
- spanning tree
- planar graphs
- polynomial time approximation
- undirected graph
- np hard
- special case
- worst case
- graph theory
- precedence constraints
- graph structure
- minimum spanning tree
- shortest path
- minimum weight
- error bounds
- partial order
- weighted graph
- dynamic programming
- approximation ratio