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
    Commented 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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .