Mucha; Sankowski (planar) (Bipartite Graph MCM Maximum Cardinality Matching)

From Algorithm Wiki
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

Reference

https://link.springer.com/article/10.1007/s00453-005-1187-5