A linear-time algorithm for finding Hamiltonian cycles in tournaments. (English) Zbl 0776.05095

The author presents an elegant algorithm for transforming a Hamilton path in an \(n\)-node tournament into a Hamiltonian cycle or into its strongly connected components, if there is no Hamiltonian cycle. Combined with a known \(O(n\log n)\) algorithm for determining a Hamiltonian path, it yields an algorithm runing in linear time with respect to the number \(m=n(n-1)/2\) of arcs which is an improvement of \(O(\log n)\) over the previously best known algorithm.


05C85 Graph algorithms (graph-theoretic aspects)
05C38 Paths and cycles
05C20 Directed graphs (digraphs), tournaments
05C45 Eulerian and Hamiltonian graphs
Full Text: DOI


[1] Camion, P., Chemins et circuits hamiltoniens des graphs complets, C.R. Acad. Sci. Paris, 249, A, 2151-2152 (1959) · Zbl 0092.15801
[2] Hell, P.; Rosenfeld, M., The complexity of finding generalized paths in tournaments, J. Algorithms, 4, 303-309 (1982) · Zbl 0532.68069
[3] Morrow, C.; Goodman, S., An efficient algorithm for finding a longest cycle in a tournament, (Proceedings 7th Southeastern Conference on Combinatorics. Proceedings 7th Southeastern Conference on Combinatorics, Graph Theory and Computing (1976), Utilitas Math: Utilitas Math Winnipeg), 453-462 · Zbl 0354.05035
[4] Soroker, D., Fast parallel algorithms for graphs and networks, (Ph.D. Thesis. Ph.D. Thesis, Rept. UCB/CSD 87/390 (1987), Computer Science Division, University of California: Computer Science Division, University of California Berkeley, CA)
[5] Soroker, D., Fast parallel algorithms for finding Hamiltonian paths and cycles in a tournament, J. Algorithms, 9, 276-286 (1988) · Zbl 0644.05036
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.