Re: [Boost-users] [BGL] Bipartite matching

From: Stephan Diederich (stephan.diederich_at_[hidden])
Date: 2006-09-14 07:24:45

Hi Firas,

2006/9/14, Swidan, Firas, Ph.D. <swidanf_at_[hidden]>:
> Hi,
>
>  I was wondering if BGL contains algorithms for (weighted and unweighted)
>  bipartite matching; the documentation site (
> http://www.boost.org/libs/graph/doc/table_of_contents.html)
> shows no trace
>  of such algorithms, neither does googling the users mailing list.

At least the unweighted bipartite matching can be solved with the
existing maxflow implementations (->
http://en.wikipedia.org/wiki/Matching ).
For the weighted case there needs to be a minimum-cost version, which
is AFIAK not implemented yet.

Cheers,
Stephan