R. Srikant et al., OPTIMAL PATH COVER PROBLEM ON BLOCK GRAPHS AND BIPARTITE PERMUTATION GRAPHS, Theoretical computer science, 115(2), 1993, pp. 351-357
The optimal path cover problem is to find a minimum number of vertex d
isjoint paths which together cover all the vertices of the graph. In t
his paper, we present linear-time algorithms for the optimal path cove
r problem for the class of block graphs and bipartite permutation grap
hs.