Chandran and Hochbaum (Bipartite Graph MCM Maximum Cardinality Matching)

Time Complexity

$O(min(V*k, E)$+sqrt(k)*min(k^{2}, E))

Space Complexity

$O(E)$?? words

(Designs a flow network and runs pseudoflow algorithms on graph; space can be reused if too many residual graphs are created)

Approximate?

Exact

Randomized?

Yes,

Model of Computation

Word RAM

Year

2011

Reference

https://arxiv.org/abs/1105.1569