Fast Parallel Algorithms for Finding Hamiltonian Paths and Cycles in a Tournament
Danny Soroker
EECS Department
University of California, Berkeley
Technical Report No. UCB/CSD-87-309
October 1986
http://www.eecs.berkeley.edu/Pubs/TechRpts/1987/CSD-87-309.pdf
A tournament is a digraph T=(V,E) in which, for every pair of vertices, u & v, exactly one of (u,v), (v,u) is in E. Two classical theorems about tournaments are that every tournament has a Hamiltonian path, and every strongly connected tournament has a Hamiltonian cycle. Furthermore, it is known how to find these in polynomial time. In this paper we discuss the parallel complexity of these problems. Our main result is that constructing a Hamiltonian path in a general tournament and a Hamiltonian cycle in a strongly connected tournament are both in NC. In addition, we give an NC algorithm for finding a Hamiltonian path with one fixed endpoint. In finding fast parallel algorithms, we also obtain new proofs for the theorems.
BibTeX citation:
@techreport{Soroker:CSD-87-309,
Author = {Soroker, Danny},
Title = {Fast Parallel Algorithms for Finding Hamiltonian Paths and Cycles in a Tournament},
Institution = {EECS Department, University of California, Berkeley},
Year = {1986},
Month = {Oct},
URL = {http://www.eecs.berkeley.edu/Pubs/TechRpts/1986/6111.html},
Number = {UCB/CSD-87-309}
}
EndNote citation:
%0 Report %A Soroker, Danny %T Fast Parallel Algorithms for Finding Hamiltonian Paths and Cycles in a Tournament %I EECS Department, University of California, Berkeley %D 1986 %@ UCB/CSD-87-309 %U http://www.eecs.berkeley.edu/Pubs/TechRpts/1986/6111.html %F Soroker:CSD-87-309