COIN-OR::LEMON - Graph Library

Opened 16 months ago

Last modified 16 months 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 16 months ago.

Download all attachments as: .zip

Change History (3)

Changed 16 months ago by alpar

comment:1 Changed 16 months 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 16 months 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.