C++ Reference: perfect_matching

This documentation is automatically generated.

Implementation of the Blossom V min-cost perfect matching algorithm. The main source for the algo is the paper: "Blossom V: A new implementation of a minimum cost perfect matching algorithm", Vladimir Kolmogorov.

The Algorithm is a primal-dual algorithm. It always maintains a dual-feasible solution. We recall some notations here, but see the paper for more details as it is well written.

TODO(user): This is a work in progress. The algo is not fully implemented yet. The initial version is closer to Blossom IV since we update the dual values for all trees at once with the same delta.

Classes

BlossomGraph
MinCostPerfectMatching