Minimum Path cover in a Directed Acyclic Graph
-
06-11-2019 - |
سؤال
Given a weighted directed acyclic graph $G=(V,D,W)$ and a set of arcs $D'$ of $D$, where the weights of $W$ are on the vertices. The problem is to partition $G$ into a minimum number of vertex-disjoint paths that cover all the vertices of $G$ subject to the constraints that:
- the weight of each path is at most $k$.
- each path should include at least one edge of $D'$.
What is the complexity of this problem?
لا يوجد حل صحيح
لا تنتمي إلى cs.stackexchange