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://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