Finding Hamilton cycles in robustly expanding digraphs - Christofides, Demetres; Keevash, Peter; Kühn, Daniela; Osthus, Deryk (Journal of Graph Algorithms and Applications, 2012)
We provide an NC algorithm for finding Hamilton cycles in directedgraphs with a certain robust expansion property. This propertycaptures several known criteria for the existence of Hamilton cycles in termsof the degree sequence and thus we provide algorithmic proofs of(i) an `oriented' analogue of Dirac's theorem and (ii)an approximate version (for directed graphs) of Chvátal's theorem.Moreover, our main result is used as a tool in a recent paper by Kühn and Osthus, which shows thatregular directed graphs of linear degree satisfying the above robust expansion property have a Hamilton decomposition,which in turn has applications to TSP tour domination. <!---->