An \(O(K\cdot n^4)\) algorithm for finding the \(K\) best cuts in a network. (English) Zbl 0505.90023
MSC:
| 90B10 | Deterministic network models in operations research |
| 90C35 | Programming involving graphs or networks |
| 05C35 | Extremal problems in graph theory |
Keywords:
finding best cuts; flow algorithms; cuts; branching technique; computational complexity; finite directed graphReferences:
| [1] | Gabow, H. N., Two algorithms for generating weighted spanning trees in order, SIAM J. Comput., 6, 139-150 (1977) · Zbl 0346.68021 |
| [2] | H. Hamacher, “Ranking the cuts of a network”, to appear as a Research Report, Department of Industrial and Systems Engineering, University of Florida, Gainsville.; H. Hamacher, “Ranking the cuts of a network”, to appear as a Research Report, Department of Industrial and Systems Engineering, University of Florida, Gainsville. · Zbl 0567.90026 |
| [3] | Karzanov, A. V., Determining the maximal flow in a network by the method of preflows, Soviet Math. Dokl., 15, 434-437 (1974) · Zbl 0303.90014 |
| [4] | Lawler, E. L., A procedure for computing the \(K\) best solutions to discrete optimization problems and its application to the shortest path problem, Management Sci., 18, 401-405 (1972) · Zbl 0234.90050 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
