Danny Soroker

EECS Department, University of California, Berkeley

Technical Report No. UCB/CSD-87-309

, 1987

http://www2.eecs.berkeley.edu/Pubs/TechRpts/1987/CSD-87-309.pdf

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.

---

BibTeX citation:

@techreport{Soroker:CSD-87-309,
    Author= {Soroker, Danny},
    Title= {Fast Parallel Algorithms for Finding Hamiltonian Paths and Cycles in a Tournament},
    Year= {1987},
    Month= {Oct},
    Url= {http://www2.eecs.berkeley.edu/Pubs/TechRpts/1987/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 1987
%@ UCB/CSD-87-309
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/1987/6111.html
%F Soroker:CSD-87-309