Bipartite Graph MCM: Difference between revisions
Jump to navigation
Jump to search
No edit summary |
No edit summary |
||
| (2 intermediate revisions by the same user not shown) | |||
| Line 12: | Line 12: | ||
== Parameters == | == Parameters == | ||
V: number of vertices | $V$: number of vertices | ||
E: number of edges | $E$: number of edges | ||
== Table of Algorithms == | == Table of Algorithms == | ||
| Line 24: | Line 24: | ||
|- | |- | ||
| [[Micali and Vazirani ( Maximum Cardinality Matching)|Micali and Vazirani]] || 1980 || $O(V^{0.5} E)$ || $O(V)$ || || Deterministic || [https:// | | [[Micali and Vazirani ( Maximum Cardinality Matching)|Micali and Vazirani]] || 1980 || $O(V^{0.5} E)$ || $O(V)$ || || Deterministic || [https://ieeexplore.ieee.org/document/4567800 Time] & [https://link.springer.com/content/pdf/10.1007/PL00009186.pdf Space] | ||
|- | |- | ||
| [[Ford–Fulkerson algorithm (Bipartite Graph MCM Maximum Cardinality Matching)|Ford–Fulkerson algorithm]] || 1956 || $O(VE)$ || $O(E)$ | | [[Ford–Fulkerson algorithm (Bipartite Graph MCM Maximum Cardinality Matching)|Ford–Fulkerson algorithm]] || 1956 || $O(VE)$ || $O(E)$ || Exact || Deterministic || [https://www.cambridge.org/core/journals/canadian-journal-of-mathematics/article/maximal-flow-through-a-network/5D6E55D3B06C4F7B1043BC1D82D40764 Time] | ||
|- | |- | ||
| [[Hopcroft–Karp algorithm (Bipartite Graph MCM Maximum Cardinality Matching)|Hopcroft–Karp algorithm]] || 1973 || $O((V^{0.5})$E) || $O(V)$ | | [[Hopcroft–Karp algorithm (Bipartite Graph MCM Maximum Cardinality Matching)|Hopcroft–Karp algorithm]] || 1973 || $O((V^{0.5})$E) || $O(V)$ || Exact || Deterministic || [https://epubs.siam.org/doi/10.1137/0202019 Time] | ||
|- | |- | ||
| [[Mucha; Sankowski (planar) (Bipartite Graph MCM Maximum Cardinality Matching)|Mucha; Sankowski (planar)]] || 2006 || $O(V^{(\omega/{2})$}) where omega is the exponent on matrix multiplication || $O( | | [[Mucha; Sankowski (planar) (Bipartite Graph MCM Maximum Cardinality Matching)|Mucha; Sankowski (planar)]] || 2006 || $O(V^{(\omega/{2})$}) where omega is the exponent on matrix multiplication || $O(V \log V)$??? || Exact || Randomized || [https://link.springer.com/article/10.1007/s00453-005-1187-5 Time] | ||
|- | |- | ||
| [[Madry's algorithm (Bipartite Graph MCM Maximum Cardinality Matching)|Madry's algorithm]] || 2013 || $O(E^{10/7}*polylog(V)$) || $O(E + V)$ || Exact || Deterministic || [https://arxiv.org/abs/1307.2205 Time] | | [[Madry's algorithm (Bipartite Graph MCM Maximum Cardinality Matching)|Madry's algorithm]] || 2013 || $O(E^{10/7}*polylog(V)$) || $O(E + V)$ || Exact || Deterministic || [https://arxiv.org/abs/1307.2205 Time] | ||
|- | |- | ||
| [[Chandran and Hochbaum (Bipartite Graph MCM Maximum Cardinality Matching)|Chandran and Hochbaum]] || 2011 || $O(min(V*k, E)$+sqrt(k)*min(k^{2}, E)) || $O(E)$ | | [[Chandran and Hochbaum (Bipartite Graph MCM Maximum Cardinality Matching)|Chandran and Hochbaum]] || 2011 || $O(min(V*k, E)$+sqrt(k)*min(k^{2}, E)) || $O(E)$?? || Exact || Randomized || [https://arxiv.org/abs/1105.1569 Time] | ||
|- | |- | ||
|} | |} | ||
| Line 41: | Line 41: | ||
[[File:Maximum Cardinality Matching - Bipartite Graph MCM - Time.png|1000px]] | [[File:Maximum Cardinality Matching - Bipartite Graph MCM - Time.png|1000px]] | ||
== Reductions FROM Problem == | == Reductions FROM Problem == | ||
Latest revision as of 09:07, 28 April 2023
Description
The goal of maximum cardinality matching is to find a matching with as many edges as possible (equivalently: a matching that covers as many vertices as possible). Here, the graph is bipartite.
Related Problems
Generalizations: General Graph MCM
Subproblem: Planar Bipartite Graph Perfect Matching
Parameters
$V$: number of vertices
$E$: number of edges
Table of Algorithms
| Name | Year | Time | Space | Approximation Factor | Model | Reference |
|---|---|---|---|---|---|---|
| Micali and Vazirani | 1980 | $O(V^{0.5} E)$ | $O(V)$ | Deterministic | Time & Space | |
| Ford–Fulkerson algorithm | 1956 | $O(VE)$ | $O(E)$ | Exact | Deterministic | Time |
| Hopcroft–Karp algorithm | 1973 | $O((V^{0.5})$E) | $O(V)$ | Exact | Deterministic | Time |
| Mucha; Sankowski (planar) | 2006 | $O(V^{(\omega/{2})$}) where omega is the exponent on matrix multiplication | $O(V \log V)$??? | Exact | Randomized | Time |
| Madry's algorithm | 2013 | $O(E^{10/7}*polylog(V)$) | $O(E + V)$ | Exact | Deterministic | Time |
| Chandran and Hochbaum | 2011 | $O(min(V*k, E)$+sqrt(k)*min(k^{2}, E)) | $O(E)$?? | Exact | Randomized | Time |
Time Complexity Graph
Reductions FROM Problem
| Problem | Implication | Year | Citation | Reduction |
|---|---|---|---|---|
| OuMv | assume: OMv then: there is no algorithm for solving incremental (or decremental) maximum cardinality bipartite matching with amortized time $O(n^{1-\epsilon})$ per insertion (or deletion) and $O(n^{2-\epsilon})$ time per query for any $\epsilon > {0}$ |
2016 | https://arxiv.org/abs/1602.06705 | link |