| Vertex partitions of r-edge-colored graphs |
| |
| 作者姓名： | JIN Ze-min~ |
| |
| 作者单位： | 1，2 |
| |
| 基金项目： | 国家自然科学基金，PCSIRT，国家重点基础研究发展计划(973计划) |
| |
| 摘 要： | Let G be an edge-colored graph.The monochromatic tree partition problem is to find the minimum number of vertex disjoint monochromatic trees to cover the all vertices of G.In the authors' previous work,it has been proved that the problem is NP-complete and there does not exist any constant factor approximation algorithm for it unless P=NP.In this paper the authors show that for any fixed integer r≥5,if the edges of a graph G are colored by r colors,called an r-edge-colored graph,the problem remains NP-complete.Similar result holds for the monochromatic path(cycle)partition problem.Therefore,to find some classes of interesting graphs for which the problem can be solved in polynomial time seems interesting. A linear time algorithm for the monochromatic path partition problem for edge-colored trees is given.
|
| 关 键 词： | 线性时间算法 有色线图 隔板 分散方法 |
Vertex partitions of r-edge-colored graphs |
| |
| JIN Ze-min.Vertex partitions of r-edge-colored graphs[J].Applied Mathematics A Journal of Chinese Universities,2008,23(1):120-126. |
| |
| Authors: | JIN Ze-min LI Xue-liang |
| |
| Institution: | [1]Center for Combinatorics and LPMC-TJKLC, Nankai University, Tianjin 300071, China. [2]Department of Mathematics, Zhejiang Normal University, Jinhua 321004, China. |
| |
| Abstract: | Let G be an edge-colored graph. The monochromatic tree partition problem is to find the minimum number of vertex disjoint monochromatic trees to cover the all vertices of G. In the authors' previous work,it has been proved that the problem is NP-complete and there does not exist any constant factor approximation algorithm for it unless P = NP. In this paper the authors show that for any fixed integer r ≥ 5,if the edges of a graph G are colored by r colors,called an r-edge-colored graph,the problem remains NP-complete. Similar result holds for the monochromatic path (cycle) partition problem. Therefore,to find some classes of interesting graphs for which the problem can be solved in polynomial time seems interesting.A linear time algorithm for the monochromatic path partition problem for edge-colored trees is given. |
| |
| Keywords: | monochromatic tree (path cycle) NP-complete linear time algorithm |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
