Skip to main content
Computer Science

Return to Question

Tweeted twitter.com/StackCompSci/status/1035180345921097728
fixed grammar, edited formatting
Source Link
edit approved Aug 29, 2018 at 7:22
Sagnik
edit approved Aug 29, 2018 at 7:22
Sagnik
  • 894
  • 7
  • 20

k $k$ vertex-disjoint paths cover in DAGDirected Acyclic Graph

The problem is that: in a directed acyclic graph G$G$, I want to know the maximum vertices that can be covered by k$k$ vertex-disjoint paths?.

Obviously, the value of k$k$ is smaller than the minimum path coverage of G$G$. Are there any approximation algorithms that can solve this problem?

k vertex-disjoint paths cover in DAG

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 Directed Acyclic Graph

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?

Source Link
Charles Xu
Charles Xu
  • 41
  • 3

k vertex-disjoint paths cover in DAG

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?