THE PATH-PARTITION PROBLEM IN BIPARTITE DISTANCE-HEREDITARY GRAPHS
Hong-Gwa Yeh, Gerard J. Chang · Taiwanese Journal of Mathematics · 1998
A path partition of a graph is a collection of vertex-disjoint paths that cover all vertices of the graph. The path-partition problem is to nd a path partition of minimum size. This paper gives a linear-time algorithm for the path-partition problem in bipartite distance-hereditary graphs.