Mucha; Sankowski (planar) (Bipartite Graph MCM Maximum Cardinality Matching)
Jump to navigation
Jump to search
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