An optimal parallel algorithm for general maximal matchings is as easy as for bipartite graphs

摘要

In this paper we show that if t_b(n,m) is the parallel time taken for computing a matching in a bipartite graph (incident with a fraction of edges) by a parallel work-optimal algorithm and if there is an algorithm A to compute a maximal matching in a general graph in t_so(n,m)-time whose cost is poly-logarithmic away from the best known serial algorithm then there is a work-optimal parallel algorithm for finding a maximal matching in a general graph that runs in time O(min{log~2 n log log n, t_b(n,m)log log n}＋t_so(n,m)). This results in an O(log~2.5 n) time optimal parallel algorithm for maximal matching in a general graph. A parallel algorithm is said to be work-optimal if the processor-time product for the algorithm is only a constant multiplicatie factor away from the best known serial algorithm.