Abstract
We present a new parallel algorithm for finding a maximal matching of a graph. The time required by our algorithm is O(TD (n) logn) and the number of processors used is PD (n), where TD (n) and PD (n) are the time and number of processors needed for a Depth First Search (DFS) of the graph.