Nenadov, Rajko
[VerfasserIn];
Steger, Angelika
[VerfasserIn];
Su, Pascal
[VerfasserIn]
;
Rajko Nenadov and Angelika Steger and Pascal Su
[MitwirkendeR]
An O(N) Time Algorithm for Finding Hamilton Cycles with High Probability
Anmerkungen:
Diese Datenquelle enthält auch Bestandsnachweise, die nicht zu einem Volltext führen.
Beschreibung:
We design a randomized algorithm that finds a Hamilton cycle in 𝒪(n) time with high probability in a random graph G_{n,p} with edge probability p ≥ C log n / n. This closes a gap left open in a seminal paper by Angluin and Valiant from 1979.