Mucha; Sankowski (planar) (Bipartite Graph MCM Maximum Cardinality Matching): Difference between revisions
Jump to navigation
Jump to search
(Created page with "== Time Complexity == $O(V^{(\omega/{2})$}) where omega is the exponent on matrix multiplication == Space Complexity == $O(VlogV)$??? words (Paper mentions matrices with O(VlogV) nonempty entries; unclear if there are any other space-consuming objects (on first passthrough) as planar graphs only require O(V) space) == Description == == Approximate? == Exact == Randomized? == Yes, Monte Carlo == Model of Computation == Word RAM == Year == 2006 == Re...") |
No edit summary |
||
| Line 5: | Line 5: | ||
== Space Complexity == | == Space Complexity == | ||
$O( | $O(V \log V)$??? words | ||
(Paper mentions matrices with O(VlogV) nonempty entries; unclear if there are any other space-consuming objects (on first passthrough) as planar graphs only require O(V) space) | (Paper mentions matrices with O(VlogV) nonempty entries; unclear if there are any other space-consuming objects (on first passthrough) as planar graphs only require O(V) space) | ||
Latest revision as of 08:55, 10 April 2023
Time Complexity
$O(V^{(\omega/{2})$}) where omega is the exponent on matrix multiplication
Space Complexity
$O(V \log V)$??? words
(Paper mentions matrices with O(VlogV) nonempty entries; unclear if there are any other space-consuming objects (on first passthrough) as planar graphs only require O(V) space)
Description
Approximate?
Exact
Randomized?
Yes, Monte Carlo
Model of Computation
Word RAM
Year
2006