Finding hamilton cycles in sparse random graphs
Finding hamilton cycles in sparse random graphs
复制标题
DOI：
10.1016/0095-8956(88)90089-5
复制
发表时间：
1987-04
期刊：
影响因子：
--
通讯作者：
A. Frieze
中科院分区：
文献类型：
--
作者：
A. Frieze
我们描述了一个多项式时间（O（n3 logn））的算法，该算法在两类具有常数平均度的随机图：Them-out模型和随机正则图模型中具有很高的概率找到汉密尔顿圈.我们还展示了如何使用该算法在稀疏随机图中找到一个大的周期。
We describe a polynomial time (O(n3logn)) algorithm which has a high probability of finding hamilton cycles in two classes of random graph which have constant average degree: them-out model and the random regular graph model. We also show how the algorithm can be used to find a large cycle in a sparse random graph.