Publication Details
Title: Optimal Parallel Algorithm for the Hamiltonian Cycle Problem on Dense Graphs
Author: E. Dahlhaus, P. Hajnal, and M. Karpinski
Group: ICSI Technical Reports
Date: June 1989
PDF: http://www.icsi.berkeley.edu/pubs/techreports/tr-89-42.pdf
Overview:
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 is optimal up to a polylogarithmic factor. The algorithm works in O((log (superscript 4)) n) 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 NC(superscript 2). 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 (1/2 - epsilon) |V| is as hard as the same problem for all graphs, and interestingly the problem of finding a Hamiltonian cycle becomes NP-complete.
Bibliographic Information:
ICSI Technical Report TR-89-042
Bibliographic Reference:
E. Dahlhaus, P. Hajnal, and M. Karpinski. Optimal Parallel Algorithm for the Hamiltonian Cycle Problem on Dense Graphs. ICSI Technical Report TR-89-042, June 1989
Author: E. Dahlhaus, P. Hajnal, and M. Karpinski
Group: ICSI Technical Reports
Date: June 1989
PDF: http://www.icsi.berkeley.edu/pubs/techreports/tr-89-42.pdf
Overview:
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 is optimal up to a polylogarithmic factor. The algorithm works in O((log (superscript 4)) n) 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 NC(superscript 2). 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 (1/2 - epsilon) |V| is as hard as the same problem for all graphs, and interestingly the problem of finding a Hamiltonian cycle becomes NP-complete.
Bibliographic Information:
ICSI Technical Report TR-89-042
Bibliographic Reference:
E. Dahlhaus, P. Hajnal, and M. Karpinski. Optimal Parallel Algorithm for the Hamiltonian Cycle Problem on Dense Graphs. ICSI Technical Report TR-89-042, June 1989