Weighted Matching general graphs

classic Classic list List threaded Threaded
2 messages Options
Reply | Threaded
Open this post in threaded view
|

Weighted Matching general graphs

Syed
Hi All,

Did anyone worked on weighted matching for general graphs? I could find the implementation of weighted matching for Bipartite graphs but not general graphs.  (Edmonds Blossom algorithm)

Can anyone guide?

Thanks,

Alee


------------------------------------------------------------------------------

_______________________________________________
jgrapht-users mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/jgrapht-users
Reply | Threaded
Open this post in threaded view
|

Re: Weighted Matching general graphs

Joris Kinable
As far as I know, nobody did this. It's actually rather involved. Here's a page from a Dutch researcher on Matching implementations: http://jorisvr.nl/maximummatching.html
I would be very happy if you implement one of the state of the art implementations in Jgraph though :).
I'm not really up to date anymore when it comes to matching implementations, but I remember there are 2 main flavors: one for sparse graphs, and one for dense graphs, each having different runtime complexities.

Joris

On Wed, Jul 29, 2015 at 10:04 PM, Ali Muhammad <[hidden email]> wrote:
Hi All,

Did anyone worked on weighted matching for general graphs? I could find the implementation of weighted matching for Bipartite graphs but not general graphs.  (Edmonds Blossom algorithm)

Can anyone guide?

Thanks,

Alee


------------------------------------------------------------------------------

_______________________________________________
jgrapht-users mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/jgrapht-users



------------------------------------------------------------------------------

_______________________________________________
jgrapht-users mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/jgrapht-users