Expose-and-merge exploration and the chromatic number of a random graph
Expose-and-merge exploration and the chromatic number of a random graph
复制标题
暴露和合并探索以及随机图的色数
DOI：
--
复制
发表时间：
1987
期刊：
影响因子：
--
通讯作者：
D. Matula
中科院分区：
文献类型：
--
作者：
D. Matula
摘要提出了一种探索随机图的暴露合并范式。描述了一个复杂度no （logn）算法，并用于证明任意边概率为0<p<1的随机图的色数落在区间内
$$\left[ {\left( {\frac{1}{2} - \varepsilon } \right)\log (1/(1 - p))\frac{n}{{\log n}}, \left( {\frac{2}{3} + \varepsilon } \right)\log (1/(1 - p))\frac{n}{{\log n}}} \right]$$
概率接近于单位asn→∞。
AbstractThe expose-and-merge paradigm for exploring random graphs is presented. An algorithm of complexitynO(logn) is described and used to show that the chromatic number of a random graph for any edge probability 0<p<1 falls in the interval
$$\left[ {\left( {\frac{1}{2} - \varepsilon } \right)\log (1/(1 - p))\frac{n}{{\log n}}, \left( {\frac{2}{3} + \varepsilon } \right)\log (1/(1 - p))\frac{n}{{\log n}}} \right]$$
with probability approaching unity asn→∞.