Parallel construction of perfect matchings and Hamiltonian cycles on dense graphs (Q1116690)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Parallel construction of perfect matchings and Hamiltonian cycles on dense graphs |
scientific article |
Statements
Parallel construction of perfect matchings and Hamiltonian cycles on dense graphs (English)
0 references
1988
0 references
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.
0 references
matching completeness
0 references
parallel algorithm
0 references
perfect matching
0 references
Hamiltonian cycle
0 references