Stay organized with collections
Save and categorize content based on your preferences.
C++ Reference: perfect_matching
Note: 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.
Except as otherwise noted, the content of this page is licensed under the Creative Commons Attribution 4.0 License, and code samples are licensed under the Apache 2.0 License. For details, see the Google Developers Site Policies. Java is a registered trademark of Oracle and/or its affiliates.
Last updated 2024-08-06 UTC.
[null,null,["Last updated 2024-08-06 UTC."],[],["The core content details the implementation of the Blossom V min-cost perfect matching algorithm, based on Vladimir Kolmogorov's paper. It's a primal-dual algorithm maintaining a dual-feasible solution. The current implementation, however, is still a work in progress and resembles Blossom IV more closely, updating dual values for all trees simultaneously. Key elements are represented by the `BlossomGraph` and `MinCostPerfectMatching` classes.\n"],null,[]]
