BIPARTITE EXPANDER MATCHING IS IN NC
David J. Haglin · Parallel Processing Letters · 1995
A work-efficient deterministic [Formula: see text] algorithm is presented for finding a maximum matching in a bipartite expander graph with any expansion factor β > 1. This improves upon a recently presented deterministic [Formula: see text] maximum matching algorithm which is restricted to those bipartite expanders with large expansion factors (β ≥ Δ∊, ∊ > 0), and is not work-efficient [1].