Building Hamiltonian Cycles in the Semi-Random Graph Process in Less Than $2n$ Rounds

Alan Frieze, Pu Gao, Calum MacRury +2

The semi-random graph process is an adaptive random graph process in which an online algorithm is initially presented an empty graph on $n$ vertices. In each round, a vertex $u$ is…