论文标题
一种用于查找高概率的汉密尔顿周期的O（n）时间算法
An O(n) time algorithm for finding Hamilton cycles with high probability
论文作者
论文摘要
我们设计了一种随机算法，该算法在$ \ mathcal {o}（n）$ time中找到汉密尔顿周期，随机图中具有很高概率的时间，带有边缘概率$ p \ ge c \ ge c \ log n / n $。这封闭了盎格鲁因（Angluin）和英勇（Valiant）从1979年开始的精确纸中的差距。
We design a randomized algorithm that finds a Hamilton cycle in $\mathcal{O}(n)$ time with high probability in a random graph $G_{n,p}$ with edge probability $p\ge C \log n / n$. This closes a gap left open in a seminal paper by Angluin and Valiant from 1979.
