Title: Path partition for graphs with special blocks
Authors: Pan, JJ
Chang, GJ
Department of Applied Mathematics
Keywords: path partition;block;complete graph;cycle;complete bipartite graph;algorithm
Issue Date: 30-Jan-2005
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. (C) 2004 Elsevier B.V. All rights reserved.
URI: http://dx.doi.org/10.1016/j.dam.2004.03.006
ISSN: 0166-218X
DOI: 10.1016/j.dam.2004.03.006
Volume: 145
Issue: 3
Begin Page: 429
End Page: 436
Appears in Collections:Articles

Files in This Item:

  1. 000226452800010.pdf