# zbMATH — the first resource for mathematics

Fats parallel algorithms for finding Hamiltonian paths and cycles in a tournament. (English) Zbl 0644.05036
A directed graph $$T=(V,E)$$ is a tournament, if for any pair u, v of vertices either (u,v)$$\in E$$ or (v,u)$$\in E$$ but not both.
Parallel NC algorithms are given for the following problems: finding a Hamiltonian path, finding a Hamiltonian path with a fixed endpoint, finding the strongly connected components, and finding a Hamiltonian cycle if T is strongly connected.
Reviewer: J.Ebert

##### MSC:
 05C45 Eulerian and Hamiltonian graphs 68R10 Graph theory (including graph drawing) in computer science 68Q25 Analysis of algorithms and problem complexity
Full Text: