Algorithms for finding K-best perfect matchings. Chegireddy, C. R. & Hamacher, H. W. Discrete Applied Mathematics, 18(2):155--165, 1987.
Algorithms for finding K-best perfect matchings [link]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