Path partition for graphs with special blocks
Journal
Discrete Applied Mathematics
Journal Volume
145
Journal Issue
3
Pages
429-436
Date Issued
2005
Author(s)
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. © 2004 Elsevier B. V. All rights reserved.
Type
journal article