A New-Old Algorithm for Minimum-cut and Maximum-flow in Closure Graphs

摘要

We present an algorithm for solving the minimum-cut problem on closure graphs without maintaining flow values. The algorithm is based on an optimization al- gorithm for the open-pit mining problem that was pre- sented in 1964(and published in 1965)by Lerchs and Grossmann. The Lerchs-Grossmann aglorithm(LG al- Gorithm)solves the maximum closure which is equiva- Lent to the minimum-cut problem. Yet, it appears sub- Stantially different from other algorithms known for Solving the minimum-cut problem and does not employ And concept of flow.