Let’s say we are talking about a simple undirected graph with no loops and no multiple edges. But not necessarily bipartite. And we need to find its matching number. Do we have to find a maximum matching first or can we just apply some “quick” spectral theory magic to get the matching number directly? And by “quickly” I mean better than $O(e\sqrt{n})$, at which point we can just use Micali-Vazirani general graph maximum matching algorithm.
$\begingroup$
$\endgroup$
2
-
$\begingroup$ MV80 didn't instantly decode to a matching algorithm for me, so you might like to make that more explicit. $\endgroup$– Ben BarberOct 31, 2021 at 15:47
-
$\begingroup$ @BenBarber, good point, replaced with a proper algorithm name and a link $\endgroup$– IterokunOct 31, 2021 at 20:18
Add a comment
|