Ford–Fulkerson 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(VE)$ == Space Complexity == $O(E)$ auxiliary words (creating new graph and using it as input to the Ford-Fulkerson algorithm) == Description == == Approximate? == Exact == Randomized? == No, deterministic == Model of Computation == Word RAM == Year == 1956 == Reference == https://www-cambridge-org.ezproxy.canberra.edu.au/core/journals/canadian-journal-of-mathematics/article/maximal-flow-through-a-network/5D6E55D3B06C4F7B1043BC1D82D40764")

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

Jump to navigation Jump to search

Time Complexity

$O(VE)$

Space Complexity

$O(E)$ auxiliary words

(creating new graph and using it as input to the Ford-Fulkerson algorithm)

Description

Approximate?

Exact

Randomized?

No, deterministic

Model of Computation

Word RAM

Year

1956

Reference

https://www-cambridge-org.ezproxy.canberra.edu.au/core/journals/canadian-journal-of-mathematics/article/maximal-flow-through-a-network/5D6E55D3B06C4F7B1043BC1D82D40764

Retrieved from "https://algorithm-wiki-csail-mit-edu.ezproxy.canberra.edu.au/w/index.php?title=Ford–Fulkerson_algorithm_(Bipartite_Graph_MCM_Maximum_Cardinality_Matching)&oldid=45252"