PTAS for Minimum k-Path Connected Vertex Cover in Growth-Bounded Graphs.
Yan ChuJianxi FanWenjun LiuCheng-Kuan LinPublished in: ICA3PP (1) (2014)
Keyphrases
- vertex cover
- approximation algorithms
- minimum cost
- spanning tree
- undirected graph
- polynomial time approximation
- np hard
- constant factor
- planar graphs
- special case
- minimum spanning tree
- worst case
- approximation guarantees
- precedence constraints
- approximation ratio
- connected components
- bipartite graph
- edge weights
- bayesian networks
- directed graph
- random walk