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

摘要

In this pa9per we show that if t_b (n,m) is the parallel time taken for computing a matching in a bipartitek grpaph (incident with a fraction of edges) by a parallel work-optimal algorihm 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~2n 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 algorihtm is said to be work-optimal if he processor-time product for the algorithm is only a constant mutiplicative facgtor awayf rom the best known serial algorithm.