Algorithms for finding k-best perfect matchings (Q1090343)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 4006301
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Algorithms for finding k-best perfect matchings |
scientific article; zbMATH DE number 4006301 |
Statements
Algorithms for finding k-best perfect matchings (English)
0 references
1987
0 references
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.
0 references
K-best perfect matching problem
0 references
binary partitioning
0 references
algorithms
0 references
0 references
0.8830973505973816
0 references
