Journal of Graph Algorithms and Applications
http://jgaa.info ISSN: 1526-1719
|
DOI: 10.7155/jgaa.00261 Finding Hamilton cycles in robustly expanding digraphs Demetres Christofides , Peter Keevash , Daniela Kühn , and Deryk Osthus Vol. 16, no. 2, pp. 335-358, 2012. Regular paper Abstract We provide an NC algorithm for finding Hamilton cycles in directed graphs with a certain robust expansion property. This property captures several known criteria for the existence of Hamilton cycles in terms of 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 that regular directed graphs of linear degree satisfying the above robust expansion property have a Hamilton decomposition, which in turn has applications to TSP tour domination.
|
Reviewed: April 2012. Revised: April 2012. Published: May 2012. Submitted: February 2009. Final: May 2012. Accepted: April 2012. Communicated by Sue Whitesides |
| Journal of Graph Algorithms and Applications |