Global min-cuts in RNC, and other ramifications of a simple min-cut algorithm 论文

摘要

This paper presents a new algorithm for nding 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 ~ O(mn 2), even if space is restricted to O(n), or can be parallelized as an RN C algorithm which runs in time O(log 2 n) 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 RN C. The algorithm does more than find a single min-cut; it nds all of them. The algorithm also yields numerous results on network reliability, enumeration of cuts, multi-way cuts, and approximate min-cuts.