On Finding the K Best Cuts in a Network. Hamacher, H. W., Picard, J.C, & Queyranne, M. *Operations Research Letters*, 2(6):303--305, March, 1984. Paper doi abstract bibtex We show that the O(K · n4) algorithm of Hamacher (1982) for finding the K best cut-sets fails because it may produce cuts rather than cut-sets. With the convention that two cuts and are different whenever X ≠ Y the K best cut problem can be solved in O(K · n4).

@article{ Hamacher1984a,
abstract = {We show that the O(K · n4) algorithm of Hamacher (1982) for finding the K best cut-sets fails because it may produce cuts rather than cut-sets. With the convention that two cuts and are different whenever X ≠ Y the K best cut problem can be solved in O(K · n4).},
author = {Hamacher, Horst W. and Picard, Jean-Claude and Queyranne, Maurice},
doi = {10.1016/0167-6377(84)90083-X},
file = {:Users/KunihiroWASA/Dropbox/paper/1984/Hamacher, Picard, Queyranne, On Finding the K Best Cuts in a Network, 1984.pdf:pdf},
issn = {01676377},
journal = {Operations Research Letters},
keywords = {Flow algorithm,cut,ranking of solutions},
month = {March},
number = {6},
pages = {303--305},
title = {{On Finding the K Best Cuts in a Network}},
url = {http://www.sciencedirect.com/science/article/pii/016763778490083X http://linkinghub.elsevier.com/retrieve/pii/016763778490083X},
volume = {2},
year = {1984}
}

Downloads: 0

{"_id":"rEjCfjkERYKeSpW7P","authorIDs":[],"author_short":["Hamacher, H.<nbsp>W.","Picard, J.C","Queyranne, M."],"bibbaseid":"hamacher-picard-queyranne-onfindingthekbestcutsinanetwork-1984","bibdata":{"abstract":"We show that the O(K · n4) algorithm of Hamacher (1982) for finding the K best cut-sets fails because it may produce cuts rather than cut-sets. With the convention that two cuts and are different whenever X ≠ Y the K best cut problem can be solved in O(K · n4).","author":["Hamacher, Horst W.","Picard, Jean-Claude","Queyranne, Maurice"],"author_short":["Hamacher, H.<nbsp>W.","Picard, J.C","Queyranne, M."],"bibtex":"@article{ Hamacher1984a,\n abstract = {We show that the O(K · n4) algorithm of Hamacher (1982) for finding the K best cut-sets fails because it may produce cuts rather than cut-sets. With the convention that two cuts and are different whenever X ≠ Y the K best cut problem can be solved in O(K · n4).},\n author = {Hamacher, Horst W. and Picard, Jean-Claude and Queyranne, Maurice},\n doi = {10.1016/0167-6377(84)90083-X},\n file = {:Users/KunihiroWASA/Dropbox/paper/1984/Hamacher, Picard, Queyranne, On Finding the K Best Cuts in a Network, 1984.pdf:pdf},\n issn = {01676377},\n journal = {Operations Research Letters},\n keywords = {Flow algorithm,cut,ranking of solutions},\n month = {March},\n number = {6},\n pages = {303--305},\n title = {{On Finding the K Best Cuts in a Network}},\n url = {http://www.sciencedirect.com/science/article/pii/016763778490083X http://linkinghub.elsevier.com/retrieve/pii/016763778490083X},\n volume = {2},\n year = {1984}\n}","bibtype":"article","doi":"10.1016/0167-6377(84)90083-X","file":":Users/KunihiroWASA/Dropbox/paper/1984/Hamacher, Picard, Queyranne, On Finding the K Best Cuts in a Network, 1984.pdf:pdf","id":"Hamacher1984a","issn":"01676377","journal":"Operations Research Letters","key":"Hamacher1984a","keywords":"Flow algorithm,cut,ranking of solutions","month":"March","number":"6","pages":"303--305","title":"On Finding the K Best Cuts in a Network","type":"article","url":"http://www.sciencedirect.com/science/article/pii/016763778490083X http://linkinghub.elsevier.com/retrieve/pii/016763778490083X","volume":"2","year":"1984","bibbaseid":"hamacher-picard-queyranne-onfindingthekbestcutsinanetwork-1984","role":"author","urls":{"Paper":"http://www.sciencedirect.com/science/article/pii/016763778490083X http://linkinghub.elsevier.com/retrieve/pii/016763778490083X"},"keyword":["Flow algorithm","cut","ranking of solutions"],"downloads":0,"html":""},"bibtype":"article","biburl":"http://www-ikn.ist.hokudai.ac.jp/~wasa/enum.bib","creationDate":"2015-04-23T04:51:44.060Z","downloads":0,"keywords":["flow algorithm","cut","ranking of solutions"],"search_terms":["finding","best","cuts","network","hamacher","picard","queyranne"],"title":"On Finding the K Best Cuts in a Network","year":1984,"dataSources":["YRMeqhMHoNu9HzJoC"]}