Summary: The paper presents a new algorithm for finding global min-cuts in weighted, undirected graphs. One of the strengths of the algorithm is its extreme simplicity. This randomized algorithm can be implemented as a strongly polynomial sequential algorithm with running time \(\tilde O(mn^ 2)\) (the notation \(\tilde O(f)\) denotes \(O(f \text{polylog} f)\)), even if space is restricted to \(O(n)\), or can be parallelized as an \({\mathcal R}{\mathcal N}{\mathcal C}\) algorithm which runs in time \(O(\log^ 2n)\) on a CRCW PRAM with \(mn^ 2\log n\) processors. In addition to yielding the best known processor bounds on unweighted graphs, this algorithm provides the first proof that the min-cut problem for weighted undirected graphs is in \({\mathcal R}{\mathcal N}{\mathcal C}\). The algorithm does more than find a single min-cut; it finds all of them. The algorithm also yields numerous results on network reliability, enumeration of cuts, multi-way cuts, and approximate min-cuts.
For the entire collection see [Zbl 0771.00043].