4
$\begingroup$

Suppose we are given a (simple) graph with non-negative edge weights, along with a matching $M$, which may or may not be max weight. I know that $M$ will be max weight if and only if the graph does not contain an $M$-augmenting path or cycle. But is there an efficient way to compute such an object? In the unweighted case, there is an efficient method for finding an augmenting path by doing a modified breadth-first-search (where for every other 'layer' of the search you take the unique matched edge available, assuming it exists), but I don't really see how this would generalize to the weighted case.

Would someone be able to verify whether or not an efficient algorithm for finding such an augmenting path/cycle exists, and possibly explain a sketch of how this works (assuming it is pretty technical) or give a reference of where to find an explanation? Any assistance would be appreciated.

$\endgroup$
1
1
$\begingroup$

You might be interested in the paper published by Vladimir Kolmogorov in Mathematical Programming Computation (MPC), July 2009, 1(1), pp. 43-67: "Blossom V: A new implementation of a minimum cost perfect matching algorithm". You can find the paper here together with a C++ implementation by the author here.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.