A path cover of a directed graph is a set of paths such
that every vertex is included in exactly one path. The size of a path cover is the number of paths in the set.
can any one tell me how to reduce the problem of finding
a minimum-sized path cover in a directed acyclic graph to the problem of
finding a maximum-sized matching in a bipartite graph. such that the total running time of the algorithm should be in O(na).
0 · ·