Algorithms for finding K-best perfect matchings. Chegireddy, C. R. & Hamacher, H. W. Discrete Applied Mathematics, 18(2):155--165, 1987. 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
{"_id":"HWJdnXzP2woWHy6mt","authorIDs":[],"author_short":["Chegireddy, C.<nbsp>R.","Hamacher, H.<nbsp>W."],"bibbaseid":"chegireddy-hamacher-algorithmsforfindingkbestperfectmatchings-1987","bibdata":{"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.","Hamacher, Horst W."],"author_short":["Chegireddy, C.<nbsp>R.","Hamacher, H.<nbsp>W."],"bibtex":"@article{ Chegireddy1987,\n 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.},\n author = {Chegireddy, Chandra R. and Hamacher, Horst W.},\n doi = {10.1016/0166-218X(87)90017-5},\n file = {:Users/KunihiroWASA/Dropbox/paper/1987/Chegireddy, Hamacher, Algorithms for finding K-best perfect matchings, 1987.pdf:pdf},\n issn = {0166218X},\n journal = {Discrete Applied Mathematics},\n number = {2},\n pages = {155--165},\n title = {{Algorithms for finding K-best perfect matchings}},\n url = {http://linkinghub.elsevier.com/retrieve/pii/0166218X87900175},\n volume = {18},\n year = {1987}\n}","bibtype":"article","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","id":"Chegireddy1987","issn":"0166218X","journal":"Discrete Applied Mathematics","key":"Chegireddy1987","number":"2","pages":"155--165","title":"Algorithms for finding K-best perfect matchings","type":"article","url":"http://linkinghub.elsevier.com/retrieve/pii/0166218X87900175","volume":"18","year":"1987","bibbaseid":"chegireddy-hamacher-algorithmsforfindingkbestperfectmatchings-1987","role":"author","urls":{"Paper":"http://linkinghub.elsevier.com/retrieve/pii/0166218X87900175"},"downloads":0,"html":""},"bibtype":"article","biburl":"http://www-ikn.ist.hokudai.ac.jp/~wasa/enum.bib","creationDate":"2015-04-23T04:51:44.493Z","downloads":0,"keywords":[],"search_terms":["algorithms","finding","best","perfect","matchings","chegireddy","hamacher"],"title":"Algorithms for finding K-best perfect matchings","year":1987,"dataSources":["YRMeqhMHoNu9HzJoC"]}