Paper doi abstract bibtex

In the K-best perfect matching problem (KM) one wants to find K pairwise different, perfect matchings M1,łdots,Mk such that w(M1) ≥ w(M2) ≥ ⋯ ≥ w(Mk) ≥ w(M), ∀M ≠ M1, M2,łdots, 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.

@article{ Chegireddy1987, abstract = {In the K-best perfect matching problem (KM) one wants to find K pairwise different, perfect matchings M1,łdots,Mk such that w(M1) ≥ w(M2) ≥ ⋯ ≥ w(Mk) ≥ w(M), ∀M ≠ M1, M2,łdots, 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.}, author = {Chegireddy, Chandra R. and Hamacher, Horst W.}, doi = {10.1016/0166-218X(87)90017-5}, file = {:Users/KunihiroWASA/Dropbox/paper/1987/Chegireddy, Hamacher, Algorithms for finding K-best perfect matchings, 1987.pdf:pdf}, issn = {0166218X}, journal = {Discrete Applied Mathematics}, number = {2}, pages = {155--165}, title = {{Algorithms for finding K-best perfect matchings}}, url = {http://linkinghub.elsevier.com/retrieve/pii/0166218X87900175}, volume = {18}, year = {1987} }

Downloads: 0