o(log4 n) time parallel maximal matching algorithm using linear number of processors

Computing maximal matching of a graph having n vertices in parallel within o \hspace{0.167em} (log^{4} \hspace{0.167em} n) time using a linear number of processors on the EREW-PRAM is an open problem [Karp, R.M. and Ramachandran, V. (1990) “Parallel algorithms for shared-memory machines”, In: van Leeuwen, J., ed., Handbook of Theoretical Computer Science, Vol. A, pp 869–941]. In this paper, we resolve this by presenting a parallel algorithm on the EREW-PRAM that works in O(log^{2} \hspace{0.167em} n \hspace{0.167em} log \hspace{0.167em} \mgreek{D} (G) \hspace{0.167em} log \ast \hspace{0.167em} n) time using O(n) number of processors, where Δ(G) is the degree of the graph.