Maximum Cardinality $f$-Matching in Time $O(n^{2/3}m)$

Harold Gabow

We present an algorithm that finds a maximum cardinality $f$-matching of a simple graph in time $O(n^{2/3}m)$. Here $f:V\to \mathbb{N}$ is a given function, and an $f$-matching is…