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

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