...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>SIAM Journal on Computing >A SPECTRAL TECHNIQUE FOR COLORING RANDOM 3-COLORABLE GRAPHS
【24h】

A SPECTRAL TECHNIQUE FOR COLORING RANDOM 3-COLORABLE GRAPHS

机译：彩色3色随机图形的光谱技术

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

Let G(3n,p,3) be a random 3-colorable graph on a set of 3n vertices generated as follows. First, split the vertices arbitrarily into three equal color classes, and then choose every pair of vertices of distinct color classes, randomly and independently, to be edges with probability p. We describe a polynomial-time algorithm that finds a proper 3-coloring of G(3n,p,3) with high probability, whenever p greater than or equal to c. where c is a sufficiently large absolute constant. This settles a problem of Blum and Spencer, who asked if an algorithm can be designed that works almost surely for p greater than or equal to polylog(n) [J. Algorithms, 19 (1995), pp. 204-234]. The algorithm can be extended to produce optimal k-colorings of random k-colorable graphs in a similar model as well as in various related models. Implementation results show that the algorithm performs very well in practice even for moderate values of c. [References: 19]
机译：令G（3n，p，3）是在按如下方式生成的一组3n个顶点上的随机三色图。首先，将顶点任意划分为三个相等的颜色类别，然后分别随机地和独立地将具有不同颜色类别的每对顶点选择为概率为p的边。我们描述了一种多项式时间算法，只要p大于或等于c / n，就可以以高概率找到G（3n，p，3）的适当3色。其中c是足够大的绝对常数。这就解决了Blum和Spencer的问题，他们询问是否可以设计出一种算法，该算法对于p大于或等于polylog（n）/ n [J.算法，19（1995），第204-234页]。该算法可以扩展为在相似模型以及各种相关模型中产生随机k可着色图的最佳k着色。实施结果表明，即使对于中等c值，该算法在实践中也表现良好。 [参考：19]

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号