Genome-scale algorithmics (GSA)

A solver for the Minimum-Cost Minimum Path Cover Problem


This is a solver for the mimimum-cost minimum path cover problem. We implemented both a minimum-weight maximum matching solution (based on Dilworth's theorem), and a minimum-cost flow solution. The latter one is the fastest one, outperforming the former even by orders of magnitude on some graphs.

The code is available here:

19.10.2014 - 19:56 Alexandru Tomescu
19.10.2014 - 19:25 Alexandru Tomescu