Add maximum matching algorithm for weighted graphs

Bug #400790 reported by Tamás Nepusz
14
This bug affects 3 people
Affects Status Importance Assigned to Milestone
igraph
New
Wishlist
Unassigned

Bug Description

A possible O(|V|*|E|*log(|V|)) algorithm can be found in:

Zvi Galil, Efficient algorithms for finding maximum matching in graphs, ACM Computing Surveys, 1986.

A Python implementation of the algorithm is here: http://www.xs4all.nl/~rjoris/maximummatching.html
There's also a C implementation: ftp://dimacs.rutgers.edu/pub/netflow/matching/weighted/solver-1

Revision history for this message
Tamás Nepusz (ntamas) wrote :

Note: the C implementation above is O(|V|^3), so it's better suited for small dense graphs. It is an implementation of the following algorithm:

H.J. Gabow, Implementation of algorithms for maximum matching on nonbipartite graphs, Stanford Ph.D thesis, 1973.

Changed in igraph:
importance: Undecided → Wishlist
Revision history for this message
Gábor Csárdi (gabor.csardi) wrote : Continue on github

The development of igraph has moved to github, so please do not comment on this bug here. You are of course welcome to comment on github, here:
https://github.com/igraph/igraph/issues/321

To post a comment you must log in.
This report contains Public information  
Everyone can see this information.

Other bug subscribers

Remote bug watches

Bug watches keep track of this bug in other bug trackers.