COIN-OR::LEMON - Graph Library

Opened 2 years ago

Last modified 2 years ago

#604 new enhancement

Faster MaxMatching implementation

Reported by: alpar Owned by: deba
Priority: major Milestone: LEMON 1.4 release
Component: core Version: hg main
Keywords: Cc: joran.van.apeldoorn@…
Revision id:

Description

From Joran van Apeldoorn:

On odd graphs it does not notice when a perfect matching (as in (n-1)/2 matched edges) is found and continues to do a BFS from the one unmatched vertex, off course without result.
This makes the running time for slightly dense graphs a lot longer on odd graphs then on even graphs, to the extend that it can take easely a 100 times longer on odd graphs.

Attachments (1)

da78005589e9.patch (2.9 KB) - added by alpar 2 years ago.

Download all attachments as: .zip

Change History (3)

Changed 2 years ago by alpar

comment:1 Changed 2 years ago by alpar

The attached changeset [da78005589e9] is a straightforward implementation of this idea. Could someone review it?

Right now only MaxMatching is modified. Shouldn't we do the same in MaxWeightedMatching, too?

comment:2 Changed 2 years ago by deba

If we stop the algorithm early, then we don't find a Gallai-Edmonds decomposition.

Otherwise, I think it's better to maintain the number of nodes in UNMATCHED status. If that goes below 2, then we can stop. It's slightly more efficient than your solution, because the number of UNMATCHED nodes decreased even if we fail to find a larger matching in a process step.

I think the same idea doesn't work for weighted matchings, because it's not guaranteed that the solution is optimal when only one node is not covered in the matching.

Note: See TracTickets for help on using tickets.