Coloring Random and Semi-Random k-Colorable Graphs
Coloring Random and Semi-Random k-Colorable Graphs
复制标题
为随机和半随机 k 可着色图着色
DOI：
--
复制
发表时间：
1995
期刊：
影响因子：
--
通讯作者：
J. Spencer
中科院分区：
文献类型：
--
作者：
Avrim Blum;J. Spencer
摘要众所周知，以最少颜色的图形着色的图是np -hard，甚至仅限于常数k≥3的k-可油图。易于k彩色研究各种图形分布，我们还提出了由Santha和Vazirani的半随机来源产生的图模型（M. Santha和U. V. Vazirani，J。Comput。SystemSci。33（1986），75-87）在此模型中，这提供了最坏情况和随机模型之间的平滑跃迁，该图是由“嘈杂的对手”生成的 - 一个对手（是否插入特定边缘）我们表明，即使对于低噪声速率，半随机k的图形也可以以高概率为最佳颜色。
Abstract The problem of coloring a graph with the minimum number of colors is well known to be NP-hard, even restricted to k -colorable graphs for constant k ≥ 3. On the other hand, it is known that random k -colorable graphs are easy to k -color. The algorithms for coloring random k -colorable graphs require fairly high edge densities, however. In this paper we present algorithms that color randomly generated k -colorable graphs for much lower edge densities than previous approaches. In addition, to study a wider variety of graph distributions, we also present a model of graphs generated by the semi-random source of Santha and Vazirani (M. Santha and U. V. Vazirani, J. Comput. System Sci. 33 (1986), 75-87) that provides a smooth transition between the worst-case and random models. In this model, the graph is generated by a "noisy adversary"-an adversary whose decisions (whether or not to insert a particular edge) have some small (random) probability of being reversed. We show that even for quite low noise rates, semi-random k -colorable graphs can be optimally colored with high probability.