標題: | Path partition for graphs with special blocks |
作者: | Pan, JJ Chang, GJ 應用數學系 Department of Applied Mathematics |
關鍵字: | path partition;block;complete graph;cycle;complete bipartite graph;algorithm |
公開日期: | 30-一月-2005 |
摘要: | 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 http://hdl.handle.net/11536/24074 |
ISSN: | 0166-218X |
DOI: | 10.1016/j.dam.2004.03.006 |
期刊: | DISCRETE APPLIED MATHEMATICS |
Volume: | 145 |
Issue: | 3 |
起始頁: | 429 |
結束頁: | 436 |
顯示於類別: | 期刊論文 |