Approximation algorithms for minimum (weight) connected k-path vertex cover.
Xiaosong LiZhao ZhangXiaohui HuangPublished in: Discret. Appl. Math. (2016)
Keyphrases
- vertex cover
- minimum weight
- approximation algorithms
- minimum cost
- spanning tree
- planar graphs
- np hard
- greedy heuristic
- bipartite graph
- minimum spanning tree
- special case
- worst case
- edge weights
- shortest path
- weighted graph
- approximation ratio
- precedence constraints
- undirected graph
- constant factor
- polynomial time approximation
- partial order
- randomized algorithm
- connected components