Manoussakis, Y. A linear-time algorithm for finding Hamiltonian cycles in tournaments. (English) Zbl 0776.05095 Discrete Appl. Math. 36, No. 2, 199-201 (1992). 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. Reviewer: H.Schmeck (Karlsruhe) Cited in 5 Documents MSC: 05C85 Graph algorithms (graph-theoretic aspects) 05C38 Paths and cycles 05C20 Directed graphs (digraphs), tournaments 05C45 Eulerian and Hamiltonian graphs Keywords:linear-time algorithm; Hamilton path; tournament; Hamiltonian cycle × Cite Format Result Cite Review PDF Full Text: DOI References: [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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.