| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 10328731 | Discrete Applied Mathematics | 2005 | 8 Pages |
Abstract
The path-partition problem is to find a minimum number of vertex-disjoint paths that cover all vertices of a given graph. This paper studies the path-partition problem from an algorithmic point of view. As the Hamiltonian path problem is NP-complete for many classes of graphs, so is the path-partition problem. The main result of this paper is to present a linear-time algorithm for the path-partition problem in graphs whose blocks are complete graphs, cycles or complete bipartite graphs.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Jun-Jie Pan, Gerard J. Chang,