Fast algorithms for finding Hamiltonian paths and cycles in in-tournament digraphs

AbstractAn in-tournament digraph is a digraph in which the set of in-neighbours of every vertex induces a tournament. For in-tournament digraphs we give O(m + n log n) algorithms to find a Hamiltonian path and a Hamiltonian cycle if they exist. Here n, m denote the number of vertices respectively arcs of the in-tournament digraph