A linear-time algorithm for finding Hamiltonian cycles in tournaments

AbstractWe give a simple algorithm to transform a Hamiltonian path in a Hamiltonian cycle, if one exists, in a tournament T of order n. Our algorithm is linear in the number of arcs, i.e., of complexity O(m)=O(n2) and when combined with the O(n log n) algorithm of [2] to find a Hamiltonian path in T, it yields an O(n2) algorithm for searching a Hamiltonian cycle in a tournament. Up to now, algorithms for searching Hamiltonian cycles in tournaments were of order O(n3) [3], or O(n2 log n) [5]