Madry's algorithm (Bipartite Graph MCM Maximum Cardinality Matching)

From Algorithm Wiki

Revision as of 12:14, 15 February 2023 by Admin (talk | contribs) (Created page with "== 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 == Reference == https://arxiv.org/abs/1307.2205")

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

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

Reference

https://arxiv.org/abs/1307.2205

Retrieved from "https://algorithm-wiki.csail.mit.edu/w/index.php?title=Madry%27s_algorithm_(Bipartite_Graph_MCM_Maximum_Cardinality_Matching)&oldid=45255"