# 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}, 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://www.eecs.berkeley.edu/Pubs/TechRpts/1986/6111.html %F Soroker:CSD-87-309