Madry's algorithm (Bipartite Graph MCM Maximum Cardinality Matching)
Jump to navigation
Jump to search
Time Complexity
$O(E^{10/7}*polylog(V)$)
Space Complexity
$O(E + V)$ words
(Derived: Uses an augmented graph (copy of the original graph plus an additional node with edges between it and all other nodes))
Description
Based on electric flows
Approximate?
Exact
Randomized?
No, deterministic
Model of Computation
Word RAM
Year
2013