Add maximum matching algorithm for weighted graphs
Bug #400790 reported by
Tamás Nepusz
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://
There's also a C implementation: ftp://dimacs.
To post a comment you must log in.
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.