Re: [Boost-users] [Graph] Maximum Cardinality Matching: weighted?

From: Jean-Francois Bastien (jfbastien_at_[hidden])
Date: 2007-07-13 06:10:38

 > Hi Jean-Francois,
> 
> Sorry, but the BGL currently doesn't have an implementation 
> of weighted matching, even for bipartite graphs. Edmonds' 
> algorithm works only on unweighted graphs.

I'd been looking for an algorithm before I found Boost's implementation
(which turns out to be a no-match for my problem); the Hungarian
algorithm seems to do the thing but it seems to be the first algorithm
developped to solve such problem and I've read it's not as good as the
latest algorithms (correct me if that's wrong).

Unfortunately the litterature gets a bit hard to read for me who know
nothing of graph theory. I'd nonetheless like to (try to) implement for
a maximum weighted maximum cardinality matching solver potentially
unbalanced complete weighted bipartite graph, and if it works out add it
to the BGL.

Which algorithm (paper or source references would be appreciated) should
I implement to do this efficiently, if not the Hungarian algorithm?

> 
> Regards,
> Aaron

JF