An improved parallel algorithm for maximal matching (Q1073571)

A parallel \(O(\log^ 3| E|)\) algorithm for finding a maximal matching in a graph G(V,E) is presented. The model of computation is the CRCW-PRAM, and \(| V| +| E|\) processors are used. This algorithm is a substantial improvement upon the two previous algorithms known to us. These algorithms by \textit{R. M. Karp} and \textit{W. Wigderson} [Proc. 16th Ann. ACM Symp. Theory of Computing, 266-272 (1984)] and \textit{G. Lev} [''Size bounds and parallel algorithms for networks'', Tech. Rep. CST-8-80, Dept. Comput. Sci., Univ. Edinburgh (1980)] achieve \(O(\log^ 4| E|)\) depth with \(| E|^ 3/\log | E|\) and \(| E| +| V|\) processors respectively. The last one though having a better performance than the first, only applies to bipartite graphs.