[Lemon-devel] Push/relabel based max.cardinality matching

[Balazs Dezso]

Dear Developers,

The comparsion of different algorithms would be nice in lemon. There is good 
reference for the bipartite maximum cardinality and weighted matching on the 
next web page:
http://www.avglab.com/andrew/soft.html
A few biparite matching problem generator and complete benchmarking is in the 
article related to mincutlib. It could be the base of our benchmarkings.

One other thing, the naming convenentions should be cleared in these 
algorithms. Now the successive shortest path and the push relabel algorithms 
are named in different manner. This should be clarified, and the new 
algorithm contains an UNDIRBIPARTITE_TYPEDEFS macro what is almost the same 
as the BPUGRAPH_TYPEDEFS

Best, Balazs

On 2007. January 25. 15:55, Alpár Jüttner wrote:
> Hi,
>
> I've just committed push-relabel type bipartite max-matching algorithms
> (lemon/bp_matching.h). It is built upon the Elevator class.
>
> It would be very interesting to see some comparison with the other
> bipartite matching algorithms available in LEMON (or even with the
> implementations that can be found on LEDA, BOOST or somewhere else on
> the web).
>
> As usual, any comment is welcome.
>
> Regards,
> Alpar
>
> _______________________________________________
> Lemon-devel mailing list
> Lemon-devel at lemon.cs.elte.hu
> http://lemon.cs.elte.hu/mailman/listinfo/lemon-devel