Algorithms for finding K-best perfect matchings |
| |
| Affiliation: | Department of Industrial & Systems Engineering and Center for Optimization and Combinatorics, University of Florida, Gainesville, FL 32611, USA |
| |
| Abstract: | In the K-best perfect matching problem (KM) one wants to find K pairwise different, perfect matchings M1,…,Mk such that w(M1) ≥ w(M2) ≥ ⋯ ≥ w(Mk) ≥ w(M), ∀M ≠ M1, M2,…, Mk. The procedure discussed in this paper is based on a binary partitioning of the matching solution space. We survey different algorithms to perform this partitioning. The best complexity bound of the resulting algorithms discussed is O(Kn3), where n is the number of nodes in the graph. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
