An O(K·n4) algorithm for finding the k best cuts in a network |
| |
| Authors: | Horst Hamacher |
| |
| Institution: | Department of Industrial and Systems Engineering, University of Florida, Gainesville, FL 32611, U.S.A. |
| |
| Abstract: | An algorithm for finding the K best cuts in a network is presented. Using a branch technique introduced by Lawler 4] we reduce the problem to K computations of 2nd best cuts. The latter problem can be solved by an O(n4) algorithm yielding an overall complexity of O(K·n4) for the presented algorithm. |
| |
| Keywords: | Flow algorithms cuts branching technique |
| 本文献已被 ScienceDirect 等数据库收录！ |
