Simple randomized parallel algorithms for finding a maximal matching in an undirected graph

摘要

The authors present simple randomized parallel algorithms for finding a maximal matching in a unidirectional graph G=(V, E) for the CRCW and CREW models. The algorithm for the CRCW model has O(log m) expected running time using m processors, where m is the number of edges in G. It is also shown that the CRCW algorithm can be implemented on a CREW PRAM (parallel random access machine). The CREW algorithm runs in O(log/sup 2/ m) time, but it requires only m/log m processors.