The path-partition problem in bipartite distance-hereditary graphs

Abstract

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 find a path partition of minimum size. This paper gives a linear-time algorithm for the path-partition problem in bipartite distance-hereditary graphs.