Parallel matching on expanders
Thomas H. Spencer · 2002
If a matching on a bipartite expander does not have maximum cardinality, it has a short augmenting path. This fact leads to an improved parallel algorithm for finding maximum cardinality matchings on such graphs. This paper describes a deterministic parallel algorithm paths that runs in (logn)/sup 4log log n+O(1)/ time on an EREW PRAM with O(nm) processors and that finds a maximum cardinality matching on an expander, n is the number of vertices of the graph and m is the number of edges of the graph.>