A simple min-cut algorithm
From MaRDI portal
Publication:4377588
DOI10.1145/263867.263872zbMath0891.68071OpenAlexW2057463094WikidataQ56572243 ScholiaQ56572243MaRDI QIDQ4377588
Publication date: 17 February 1998
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: http://www.acm.org/pubs/contents/journals/jacm/1997-44/
Related Items (77)
Minimum Cuts in Surface Graphs ⋮ Cache Oblivious Minimum Cut ⋮ Faster Algorithms for Next Breakpoint and Max Value for Parametric Global Minimum Cuts ⋮ A min-cut approach to functional regionalization, with a case study of the Italian local labour market areas ⋮ Minimum degree orderings ⋮ Time constrained maximal covering salesman problem with weighted demands and partial coverage ⋮ Minimum Cuts and Sparsification in Hypergraphs ⋮ Parameterized algorithms for min-max multiway cut and list digraph homomorphism ⋮ Decision-based scenario clustering for decision-making under uncertainty ⋮ A branch‐and‐cut algorithm for the ring spur assignment problem ⋮ Personal reminiscence: combinatorial and discrete optimization problems in which I have been interested ⋮ Data Analytics on Graphs Part I: Graphs and Spectra on Graphs ⋮ Data Analytics on Graphs Part III: Machine Learning on Graphs, from Graph Topology to Applications ⋮ Inverse maximum capacity problems ⋮ Polynomial-time algorithms for multimarginal optimal transport problems with structure ⋮ Constrained and bicriteria inverse bottleneck optimization problems under weighted Hamming distance ⋮ Computing Area-Optimal Simple Polygonizations ⋮ An optimal pruned traversal tree-based fast minimum cut solver in dense graph ⋮ Minimum Cut and Minimum k -Cut in Hypergraphs via Branching Contractions ⋮ On the edge-connectivity and restricted edge-connectivity of optimal 1-planar graphs ⋮ Solving graph partitioning on sparse graphs: cuts, projections, and extended formulations ⋮ Strongly polynomial bounds for multiobjective and parametric global minimum cuts in graphs and hypergraphs ⋮ Divide-and-conquer algorithms for partitioning hypergraphs and submodular systems ⋮ The Complexity of Boolean Surjective General-Valued CSPs ⋮ Generalized cut trees for edge-connectivity ⋮ Hybridizing evolutionary algorithms with variable-depth search to overcome local optima ⋮ A note on the minimization of symmetric and general submodular functions ⋮ Minimum Cuts and Shortest Cycles in Directed Planar Graphs via Noncrossing Shortest Paths ⋮ Partitioning planar graphs: a fast combinatorial approach for max-cut ⋮ A combinatorial model and algorithm for globally searching community structure in complex networks ⋮ Models and methods for solving the problem of network vulnerability ⋮ New algorithms for a simple measure of network partitioning ⋮ Hearing the clusters of a graph: A distributed algorithm ⋮ Weight reduction problems with certain bottleneck objectives. ⋮ Constrained Graph Partitioning via Matrix Differential Equations ⋮ Cuts in undirected graphs. I ⋮ Complexity of the min-max (regret) versions of min cut problems ⋮ Cardinality constrained minimum cut problems: complexity and algorithms. ⋮ Certifying algorithms ⋮ Practical Minimum Cut Algorithms ⋮ Approximating Spectral Clustering via Sampling: A Review ⋮ LP Relaxation and Tree Packing for Minimum $k$-Cut ⋮ Fast and Deterministic Approximations for k-Cut. ⋮ Finding densest \(k\)-connected subgraphs ⋮ Efficient and Adaptive Parameterized Algorithms on Modular Decompositions ⋮ Decomposition-by-normalization (DBN): leveraging approximate functional dependencies for efficient CP and Tucker decompositions ⋮ A comparison of algorithms for finding an efficient theme park tour ⋮ On the complexity of computing the \(k\)-restricted edge-connectivity of a graph ⋮ On minimum 3-cuts and approximating k-cuts using Cut Trees ⋮ A new?old algorithm for minimum-cut and maximum-flow in closure graphs ⋮ On graphs of the cone decompositions for the min-cut and max-cut problems ⋮ The prize-collecting generalized minimum spanning tree problem ⋮ Exact algorithms for cluster editing: Evaluation and experiments ⋮ A decomposition algorithm for the ring spur assignment problem ⋮ Graph connectivity and its augmentation: Applications of MA orderings ⋮ A fast algorithm for cactus representations of minimum cuts ⋮ Unnamed Item ⋮ Graph clustering, variational image segmentation methods and Hough transform scale detection for object measurement in images ⋮ Local Flow Partitioning for Faster Edge Connectivity ⋮ Unnamed Item ⋮ Connectivity interdiction ⋮ Topological optimization of reliable networks under dependent failures ⋮ Minimum Cuts of Simple Graphs in Almost Always Linear Time ⋮ Computing vertex-disjoint paths in large graphs using MAOs ⋮ New algorithms for a simple measure of network partitioning ⋮ Computing minimum multiway cuts in hypergraphs ⋮ Diffuse Interface Models on Graphs for Classification of High Dimensional Data ⋮ Unnamed Item ⋮ Symmetric submodular system: contractions and Gomory-Hu tree ⋮ On the Complexity of Computing the k-restricted Edge-connectivity of a Graph ⋮ Finding minimum 3-way cuts in hypergraphs ⋮ Minimizing symmetric submodular functions ⋮ I/O efficient algorithms for the minimum cut problem on unweighted undirected graphs ⋮ Parametric analysis of overall min-cuts and applications in undirected networks. ⋮ A Branch-Price-and-Cut Algorithm for Packing Cuts in Undirected Graphs ⋮ Hypergraph k-Cut for Fixed k in Deterministic Polynomial Time ⋮ An FPT algorithm for matching cut and d-cut
Uses Software
This page was built for publication: A simple min-cut algorithm
