|
|||||
|
|
On finding the K best cuts in a network |
|
| Authors: | Horst W Hamacher Jean-Claude Picard Maurice Queyranne |
| Institution: | Department of Industrial and Systems Engineering, University of Florida, Gainesville, FL 32611, USA;Département des Sciences Administratives, Université du Quebec á Montréal, Montréal, Qué. H3C 3P8, Canada;Faculty of Commerce and Business Administration, University of British Columbia, Vancouver, B.C. V6T 1Y8, Canada |
| 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). |
| Keywords: | Flow algorithm cut ranking of solutions |
| 本文献已被 ScienceDirect 等数据库收录！ | |