Practical minimum cut algorithms
From MaRDI portal
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.
Recommendations
Cites work
- scientific article; zbMATH DE number 437577 (Why is no real title available?)
- scientific article; zbMATH DE number 742961 (Why is no real title available?)
- scientific article; zbMATH DE number 2119685 (Why is no real title available?)
- scientific article; zbMATH DE number 6472607 (Why is no real title available?)
- (Semi-)External Algorithms for Graph Partitioning and Clustering
- A Branch-and-Cut Algorithm for the Resolution of Large-Scale Symmetric Traveling Salesman Problems
- A new approach to the maximum-flow problem
- A new approach to the minimum cut problem
- A randomized fully polynomial time approximation scheme for the all-terminal network reliability problem
- A simple min-cut algorithm
- An Improved Min-Cut Algonthm for Partitioning VLSI Networks
- An efficient algorithm for the minimum capacity cut problem
- An improved equivalence algorithm
- Computing Edge-Connectivity in Multigraphs and Capacitated Graphs
- Counting almost minimum cutsets with reliability applications
- Deterministic global minimum cut of a simple graph in near-linear time
- Experimental and Efficient Algorithms
- Fast algorithms for determining (generalized) core groups in social networks
- Generating Random Hyperbolic Graphs in Subquadratic Time
- Implementing an efficient minimum capacity cut algorithm
- Local flow partitioning for faster edge connectivity
- Maximal Flow Through a Network
- Minimum cuts in near-linear time
- Multi-Terminal Network Flows
- On the Analysis of a Label Propagation Algorithm for Community Detection
- Practical performance of efficient minimum cut algorithms
Cited in
(17)- Speeding up the Gomory-Hu parallel cut tree algorithm with efficient graph contractions
- Integer Programming and Combinatorial Optimization
- A distributed mincut/maxflow algorithm combining path augmentation and push-relabel
- Implementing an efficient minimum capacity cut algorithm
- A new contraction technique with applications to congruency-constrained cuts
- Massively Parallel Algorithms for Minimum Cut
- Graph bisection with Pareto-optimization
- In search of dense subgraphs: How good is greedy peeling?
- Two‐stage stochastic minimum s − t cut problems: Formulations, complexity and decomposition algorithms
- scientific article; zbMATH DE number 7651198 (Why is no real title available?)
- Practical minimum cut algorithms
- scientific article; zbMATH DE number 1783770 (Why is no real title available?)
- Fully-dynamic min-cut
- Graph bisection with Pareto optimization
- Minimum cuts in near-linear time
- Fundamentals of Computation Theory
- Reccs: realistic cluster connectivity simulator for synthetic network generation
This page was built for publication: Practical minimum cut algorithms
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4629534)
