Department of Computer Science
Chair V

University of Bonn -> Department of Computer Science -> Chair V
CS-Reports 1985-1989 Copyright 1985-1989 University of Bonn, Department of Computer Science, Abt. V


Optimal Parallel Algorithm for the Hamiltonian Cycle Problem on Dense Graphs
Elias Dahlhaus, Péter Hajnal and Marek Karpinski
[Download PostScript] [Download PDF]

Dirac's classical theorem asserts that, if every vertex of a graph G on n vertices has degree at least n/2 then G has a Hamiltonian cycle. We give a fast parallel algorithm on a CREW-PRAM to find a Hamiltonian cycle in such graphs. Our algorithm uses a linear number of processors and its optimal up to a polylogarithmic factor. The algorithm works in O(log4n) parallel time and uses linear number of processors on a CREW-PRAM. Our method bears some resemblance to Anderson's RNC algorithm [An] for maximal paths: we, too, start from a system of disjoint paths and try to glue them together. We are, however, able to perform the base step (perfect matching) deterministically.
We also prove that a perfect matching in dense graphs can be found in NC2. The cost of improved time is a quadratic number of processors.
On the negative side, we prove that finding an NC algorithm for perfect matching in slightly less dense graphs (minimum degree is at least (1/2 - ε)|V|) is as hard as the same problem for all graphs, and interestingly the problem of finding a Hamiltonian cycle become NP-complete.

Last Change: 12/05/08 at 12:10:35
University of Bonn -> Department of Computer Science -> Chair V