The problem is that: in a directed acyclic graph G, I want to know the maximum vertices that can be covered by k vertex-disjoint paths? Obviously, the value of k is smaller than the minimum path coverage of G. Are there any approximation algorithms that can solve this problem?
k vertex-disjoint paths cover in DAG
Charles Xu
- 41
- 3