Parallel construction of perfect matchings and Hamiltonian cycles on dense graphs

AbstractThe intensive study of fast parallel and distributed algorithms for various routing (and communications) problems on graphs with good expanding properties [29, 30, 33] has been carried out recently. The parallel solutions for expanders that already exist [30] required an extensive randomization and an application of a randomized subroutine for the Maximum Matching Problem. In this paper we attack the problem of fast parallel algorithms for constructing perfect matchings and Hamiltonian cycles on dense graph-networks (undirected graphs of minimal degree 12¦V¦). Somewhat surprisingly, we design fast deterministic parallel algorithms for constructing both the perfect matchings and the Hamiltonian cycles on the dense graphs.The algorithm for constructing perfect matchings on dense graphs works in O(log2 n) parallel time and O(n8) processors, or O(log4 n) parallel time and O(n4) processors on a CREW-PRAM. The algorithm for constructing Hamiltonian cycles on dense graphs works in O(log5 n) parallel time and O(n4) processors on a CREW-PRAM.Our method of the parallel solution involves a development of new dense graph combinatorics suitable for fast parallelization