What can be recommended for finding optimal perfect matchings in large bipartite graphs with small vertex degree if the edge-weights are positive real values?

I am looking for algorithms of which freely available implementations exist or that don't require heavy machinery for implementation.

Apart from that I am also looking for graph modifications that can speed up the calculation of the optimal matching edges; subtracting vertex potentials may be in that vein.

  • $\begingroup$ The fractional matching polytope is equal to the matching polytope for bipartite graphs, so you can just solve a small linear program. $\endgroup$ – Tony Huynh May 24 at 11:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.