Danny Soroker
EECS Department
University of California, Berkeley
Technical Report No. UCB/CSD-87-309
October 1986
http://www2.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://www2.eecs.berkeley.edu/Pubs/TechRpts/1986/6111.html}, Number = {UCB/CSD-87-309}, Abstract = {A tournament is a digraph <i>T</i>=(<i>V</i>,<i>E</i>) in which, for every pair of vertices, <i>u</i> & <i>v</i>, exactly one of (<i>u</i>,<i>v</i>), (<i>v</i>,<i>u</i>) is in <i>E</i>. 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 <i>NC</i>. In addition, we give an <i>NC</i> algorithm for finding a Hamiltonian path with one fixed endpoint. In finding fast parallel algorithms, we also obtain new proofs for the theorems.} }
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://www2.eecs.berkeley.edu/Pubs/TechRpts/1986/6111.html %F Soroker:CSD-87-309