Algorithms for maximum k-colorings and k-coverings of transitive graphs
Algorithms for maximum k-colorings and k-coverings of transitive graphs
复制标题
传递图的最大 k 着色和 k 覆盖的算法
DOI：
10.1002/net.3230170407
复制
发表时间：
1987
期刊：
影响因子：
2.1
通讯作者：
F. Gavril
中科院分区：
文献类型：
--
作者：
F. Gavril
考虑一个图G和一个正整数k，最大k着色问题是使用k种颜色为最大数量的顶点上色，这样相邻的两个顶点没有相同的颜色。最大k覆盖问题是找到k个覆盖最大数量顶点的不相交团。本文包含了寻找传递图的最大k色和最大k覆盖的多项式时间算法。
Consider a graph G and a positive integer k. The maximum k-coloring problem is to color a maximum number of vertices using k colors, such that no two adjacent vertices have the same color. The maximum k-covering problem is to find k disjoint cliques covering a maximum number of vertices. The present paper contains polynomial time algorithms for finding maximum k-colorings and maximum k-coverings of transitive graphs.