On the minimum monochromatic or multicolored subgraph partition problems
On the minimum monochromatic or multicolored subgraph partition problems
复制标题
关于最小单色或多色子图划分问题
DOI：
10.1016/j.tcs.2007.04.033
复制
发表时间：
2007-10
影响因子：
1.1
通讯作者：
张晓岩
中科院分区：
文献类型：
--
作者：
李学良;张晓岩
设G=（V，E）是一个边色图。如果子图H的所有边的颜色都相同，则子图H是单色的；如果子图H的两条边的颜色都不相同，则子图H是多色的。我们研究了寻找单色或多色子图的最小数量问题的复杂性，如团，循环，树和路径，划分V(G)，这取决于所使用的颜色的数量和颜色在颜色中出现的最大次数。对于无K4−的图G（其中m为G中最大的单色团的大小）求单色团划分V(G)的最小数目的问题，我们也给出了一个贪心格式，该格式产生了一个(lnm+1)-逼近。通过对逼近算法的稍微修改，它可以用于多色情况。我们证明，除非NP DTIME(NO(loglogN))，对于任意λ≥0，不存在寻找性能为50/521(1−λ)ln|V|的多色树分区V(G)的最小数量的近似算法。
Let G=(V,E) be an edge-colored graph. A subgraph H is said to be monochromatic if all the edges of H have the same color, and multicolored if no two edges of H have the same color. We investigate the complexity of the problems for finding the minimum number of monochromatic or multicolored subgraphs, such as cliques, cycles, trees and paths, partitioning V(G), depending on the number of colors used and the maximal number of times a color appears in a coloring. We also present a greedy scheme that yields a (lnm+1)-approximation for the problem of finding the minimum number of monochromatic cliques partitioning V(G) for a K4−-free graph G, where m is the size of the largest monochromatic clique in G. By a slightly modification of the approximation algorithm, it can be used for the multicolored case. We show that unless NP⊆DTIME(NO(loglogN)), for any ϵ≥0 there is no approximation algorithm for finding the minimum number of multicolored trees partitioning V(G) with performance 50/521(1−ϵ)ln|V|.
登录
查看更多内容
影响因子：
1.8
作者：
Zemin Jin;Xueliang Li
通讯作者：
Zemin Jin;Xueliang Li
DOI：
10.1006/jctb.1996.0065
发表时间：
1996-11
期刊：
J. Comb. Theory, Ser. B
影响因子：
--
作者：
P. Haxell;Y. Kohayakawa
通讯作者：
P. Haxell;Y. Kohayakawa
影响因子：
0.9
作者：
A. Kaneko;M. Kano;Kazuhiro Suzuki
通讯作者：
A. Kaneko;M. Kano;Kazuhiro Suzuki
DOI：
10.1006/jctb.1997.1737
发表时间：
1997-03
期刊：
J. Comb. Theory B
影响因子：
--
作者：
P. Haxell
通讯作者：
P. Haxell
DOI：
10.1016/s0167-5060(08)70377-7
发表时间：
1993
期刊：
Annals of discrete mathematics
影响因子：
--
作者：
P. Erdos;Z. Tuza
通讯作者：
P. Erdos;Z. Tuza