Parallel construction of perfect matchings and Hamiltonian cycles on dense graphs (Q1116690)

The authors present a parallel algorithm, which constructs for each graph of minimal degree 1/2 n a perfect matching and a Hamiltonian cycle. Sequential constructive proofs of the existence of perfect matchings and Hamiltonian cycles are due to König and Dirac, respectively. For lower degree ratios the authors prove, that the perfect matching problem is as hard as the general perfect matching problem. That means, a polylog time polynomial processor algorithm of a minimal degree \(a\cdot n\) for a smaller than 1/2 would imply the existence of such an algorithm for the general perfect matching problem.