標題: 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
顯示於類別:期刊論文


文件中的檔案:

  1. 000226452800010.pdf