N-processors graphs distributively achieve perfect matchings in O(log2N) beats
Eli Shamir, Eli Upfal · 1982
A perfect matching in a graph G(V,E), also called a 1-factor, is a collection P of non-interesting edges engaging (incident with) all the vertices; in case G is bipartite V = M @@@@ F, M @@@@ F = φ, P should engage all the vertices of M. The combinatorial problem of finding a perfect matching in G (and its rich ramifications) were extensively studied (and applied) from existential, algorithmic and probabilistic points of view.