pathcover..

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.

Howdy, Stranger!

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

Categories