pathcover.. - Programmers Heaven

Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!

Categories

pathcover..

ksr008ksr008 Posts: 1Member
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).
Sign In or Register to comment.