
University of Bonn > Department of Computer Science > Chair V  
CSReports 19851989  Copyright 19851989 University of Bonn, Department of Computer Science, Abt. V  
8527 05.12.2008 
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 CREWPRAM 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(log^{4}n) parallel time and uses linear number of processors on a CREWPRAM. 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. 

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