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.
Original language | English |
---|---|
Pages (from-to) | 353-360 |
Number of pages | 8 |
Journal | Taiwanese Journal of Mathematics |
Volume | 2 |
Issue number | 3 |
DOIs | |
State | Published - Sep 1998 |
Keywords
- Distance-hereditary graph
- Hamiltonian path
- Path partition