Algorithms for finding k-best perfect matchings (Q1090343)

In the K-best perfect matching problem (KM) one wants to find K pairwise different, perfect matchings \(M_ 1,...,M_ k\) such that \(w(M_ 1)\geq w(M_ 2)\geq...\geq w(M_ k)\geq w(M)\), \(\forall M\neq M_ 1,M_ 2,...,M_ k\). 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(Kn^ 3)\), where n is the number of nodes in the graph.