The minimum cut problem for an undirected edge-weighted graph asks us to divide its set of nodes into two blocks while minimizing the weighted sum of the cut edges. In this paper, we engineer the fastest known exact algorithm for the problem. State-of-the-art algorithms like the algorithm of Padberg and Rinaldi or the algorithm of Nagamochi, Ono and Ibaraki identify edges that can be contracted to reduce the graph size such that at least one minimum cut is maintained in the contracted graph. Our algorithm achieves improvements in running time over these algorithms by a multitude of techniques. First, we use a recently developed fast and parallel inexact minimum cut algorithm to obtain a better bound for the problem. Afterwards, we use reductions that depend on this bound to reduce the size of the graph much faster than previously possible. We use improved data structures to further lower the running time of our algorithm. Additionally, we parallelize the contraction routines of Overall, we arrive at a system that significantly outperforms the fastest state-of-the-art solvers for the exact minimum cut problem.
Nagamochi al @cite_0 @cite_9 give a minimum cut algorithm which does not use any flow computations. Instead, their algorithm uses maximum spanning forests to find a non-empty set of contractible edges. This contraction algorithm is run until the graph is contracted into a single node. The algorithm has a running time of @math . Stoer and Wagner @cite_19 give a simpler variant of the algorithm of Nagamochi, Ono and Ibaraki @cite_9 , which has a the same asymptotic time complexity. The performance of this algorithm on real-world instances, however, is significantly worse than the performance of the algorithms of Nagamochi, Ono and Ibaraki or Hao and Orlin, as shown in experiments conducted by J "unger al @cite_12 . Both the algorithms of Hao and Orlin, and Nagamochi, Ono and Ibaraki achieve close to linear running time on most benchmark instances @cite_14 @cite_12 . To the best of our knowledge, there are no parallel implementation of either algorithm. Both of the algorithms do not have a straightforward parallel implementation.
@cite_14 @cite_9 @cite_0 @cite_19 @cite_12
2032591091 2042852020 2035228443 2057463094 2002516237
Recently, several new algorithms have been developed for the minimum cut problem that substantially improve worst-case time bounds for the problem. These algorithms are very different from the earlier ones and from each other. We conduct an experimental evaluation of the relative performance of these algorithms. In the process, we develop heuristics and data structures that substantially improve practical performance of the algorithms. We also develop problem families for testing minimum cut algorithms. Our work leads to a better understanding of practical performance of the minimum cut algorithms and produces very efficient codes for the problem. In this paper, we present an efficient implementation of theO(mn + n2 logn) time algorithm originally proposed by Nagamochi and Ibaraki (1992) for computing the minimum capacity cut of an undirected network. To enhance computation, various ideas are added so that it can contract as many edges as possible in each iteration. To evaluate the performance of the resulting implementation, we conducted extensive computational experiments, and compared the results with that of Padberg and Rinaldi's algorithm (1990), which is currently known as one of the practically fastest programs for this problem. The results indicate that our program is considerably faster than Padberg and Rinaldi's program, and its running time is not significantly affected by the types of the networks being solved. Given an undirected graph @math , it is known that its edge-connectivity @math can be computed by solving @math max-flow problems. The best time bounds known for the problem are @math , due to Matula (28th IEEE Symposium on the Foundations of Computer Science, 1987, pp. 249–251) if G is simple, and @math , due to Even and Tarjan (SIAM J. Comput., 4 (1975), pp. 507–518) if G is multiple.An @math time algorithm for computing the edge-connectivity @math of a multigraph @math , where @math is the number of pairs of nodes between which G has an edge, is proposed. This algorithm does not use any max-flow algorithm but consists only of @math times of graph searches and edge contractions. This method is then extended to a capacitated network to compute its minimum cut capacity in @math time. We present an algorithm for finding the minimum cut of an undirected edge-weighted graph. It is simple in every respect. It has a short and compact description, is easy to implement, and has a surprisingly simple proof of correctness. Its runtime matches that of the fastest algorithm known. The runtime analysis is straightforward. In contrast to nearly all approaches so far, the algorithm uses no flow techniques. Roughly speaking, the algorithm consists of about | V | nearly identical phases each of which is a maximum adjacency search . In the late eighties and early nineties, three major exciting new developments (and some ramifications) in the computation of minimum capacity cuts occurred and these developments motivated us to evaluate the old and new methods experimentally. We provide a brief overview of the most important algorithms for the minimum capacity cut problem and compare these methods both with problem instances from the literature and with problem instances originating from the solution of the traveling salesman problem by branch-and-cut.