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

Manoussakis, Y.

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)

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

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