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, (), 453-462 · Zbl 0354.05035
[4]	Soroker, D., Fast parallel algorithms for graphs and networks, ()
[5]	Soroker, D., Fast parallel algorithms for finding Hamiltonian paths and cycles in a tournament, J. algorithms, 9, 276-286, (1988) · Zbl 0644.05036