Back to Search
Start Over
Path partition for graphs with special blocks
- Source :
-
Discrete Applied Mathematics . Jan2005, Vol. 145 Issue 3, p429-436. 8p. - Publication Year :
- 2005
-
Abstract
- 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. [Copyright &y& Elsevier]
- Subjects :
- *COMPUTATIONAL mathematics
*GRAPH theory
*ALGORITHMS
*TOPOLOGY
Subjects
Details
- Language :
- English
- ISSN :
- 0166218X
- Volume :
- 145
- Issue :
- 3
- Database :
- Academic Search Index
- Journal :
- Discrete Applied Mathematics
- Publication Type :
- Academic Journal
- Accession number :
- 19274593
- Full Text :
- https://doi.org/10.1016/j.dam.2004.03.006