1
$\begingroup$

How would one find a minimum-weight perfect 2-matching of a general graph? Is it possible to use standard matching techniques like Blossom V?

A minimum-weight perfect 2-matching of a graph G is a subgraph M of minimal total edge weight, such that each vertex in G is incident by exactly 2 edges from M.

$\endgroup$
1
$\begingroup$

From an answer to my other question it turns out that one can convert this problem to standard matching.

Find a minimum-weight perfect b-matching, where b is even

I still wonder whether this would give the most efficient approach?

$\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.