Practical Minimum Cut Algorithms

Abstract

The minimum cut problem for an undirected edge-weighted graph asks us to divide its set of nodes into two blocks while minimizing the weight sum of the cut edges. Here, we introduce a linear-time algorithm to compute near-minimum cuts. Our algorithm is based on cluster contraction using label propagation and Padberg and Rinaldi's contraction heuristics [SIAM Review, 1991]. We give both sequential and shared-memory parallel implementations of our algorithm. Extensive experiments on both real-world and generated instances show that our algorithm finds the optimal cut on nearly all instances significantly faster than other state-of-the-art algorithms while our error rate is lower than that of other heuristic algorithms. In addition, our parallel algorithm shows good scalability.

References in corpus (3)

• Near linear time algorithm to detect community structures in large-scale networks
• Hyperbolic Geometry of Complex Networks
• (Semi-)External Algorithms for Graph Partitioning and Clustering

Cited by in corpus (2)

• Scalable Graph Algorithms
• Algorithm Engineering for Cut Problems