A Parallel Maximal Matching Algorithm for Undirected Graphs with Applications
无向图的边极大匹配并行算法及其应用

A fast and optimal parallel maximal matching algorithm is proposed for a class of graphs. It runs in O(logn) time with O((n+m)/logn) processors on a EREW PRAM (exclusive-read and exclusive-write parallel random access machine).