Random graph coloring: statistical physics approach.
Random graph coloring: statistical physics approach.
复制标题
随机图着色：统计物理方法。
DOI：
--
复制
发表时间：
2002
期刊：
影响因子：
--
通讯作者：
D. Saad
中科院分区：
文献类型：
--
作者：
J. V. Mourik;D. Saad
利用统计物理和概率论的方法研究了随机图的顶点着色问题。我们的分析结果相比，精确枚举和Monte Carlo模拟。我们批判性地讨论了各种方法的优点和缺点，并解释所获得的结果。我们提出了一个精确的解析表达式的双染色问题以及一般副本对称近似解的热力学的p颜色和K体边的图染色问题。
The problem of vertex coloring in random graphs is studied using methods of statistical physics and probability. Our analytical results are compared to those obtained by exact enumeration and Monte Carlo simulations. We critically discuss the merits and shortcomings of the various methods, and interpret the results obtained. We present an exact analytical expression for the two-coloring problem as well as general replica symmetric approximated solutions for the thermodynamics of the graph coloring problem with p colors and K-body edges.