Path cover
From Wikipedia, the free encyclopedia
Given a directed graph G = (V,E), a vertex-disjoint path cover is a set of vertex-disjoint directed paths such that every vertex 
belongs to exactly one path. Note that a path cover may include paths of length 0 (a single vertex).
Given a digraph G, The minimum path cover problem consists of finding a path cover for G having the least number of paths. The related decision problem is NP-complete since it contains the Hamiltonian path problem as a special case. The problem is however solvable in polynomial time for a number of classes of digraphs.
[edit] External links
- D. S. Franzblau, A. Raychaudhuri Optimal Hamiltonian completions and path covers for trees, and a reduction to maximum flow
