4
$\begingroup$

Question:
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.

Improve this question
$\endgroup$
1
  • 1
    $\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, 2020 at 11:13

1 Answer 1

Reset to default
1
$\begingroup$

pyMCFSimplex seems to best fit my needs. "It is a free Python port of a Python Wrapper for MCFSimplex. pyMCFimplex is a Python-Wrapper for the C++ MCFSimplex Solver Class from the Operations Research Group at the University of Pisa. MCFSimplex is a piece of software hat solves big sized Minimum Cost Flow Problems very fast through the (primal or dual) network simplex algorithm."

scipy.sparse.csgraph.min_weight_full_bipartite_matching is an alternative

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.