The complexity for partitioning graphs by monochromatic trees, cycles and paths
The complexity for partitioning graphs by monochromatic trees, cycles and paths
复制标题
DOI：
10.1080/00207160412331290685
复制
发表时间：
2004-11
影响因子：
1.8
通讯作者：
Zemin Jin;Xueliang Li
中科院分区：
文献类型：
--
作者：
Zemin Jin;Xueliang Li
设G是边色图。本文证明了寻找覆盖图G的顶点的最小不相交单色树的最小数目是NP-困难的，并且证明了除非P=NP，否则不存在求解该问题的恒因子近似算法。同样的结果也适用于寻找覆盖图的顶点的最小数目的不相交单色圈(分别是路)的问题。
Let G be an edge-coloured graph. We show in this paper that it is NP-hard to find the minimum number of vertex disjoint monochromatic trees which cover the vertices of the graph G. We also show that there is no constant factor approximation algorithm for the problem unless P = NP. The same results hold for the problem of finding the minimum number of vertex disjoint monochromatic cycles (paths, respectively) which cover the vertices of the graph.