A new approach to the minimum cut problem
From MaRDI portal
Publication:4371680
DOI10.1145/234533.234534zbMath0882.68103OpenAlexW2168919539WikidataQ56385868 ScholiaQ56385868MaRDI QIDQ4371680
Clifford Stein, David R. Karger
Publication date: 22 January 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/1996-43/
Graph theory (including graph drawing) in computer science (68R10) Parallel algorithms in computer science (68W10)
Related Items
Tracking Paths, Cache Oblivious Minimum Cut, Faster Algorithms for Next Breakpoint and Max Value for Parametric Global Minimum Cuts, Introduction to QUBO, A branch-and-cut algorithm for the vehicle routing problem with two-dimensional loading constraints, Recent developments in maximum flow algorithms, Minimum cost subpartitions in graphs, The label cut problem with respect to path length and label frequency, An approach to the asymmetric multi-depot capacitated arc routing problem, Minimum degree orderings, Efficient algorithms for the problems of enumerating cuts by non-decreasing weights, An Improved Integrality Gap for Asymmetric TSP Paths, Minimum Cuts and Sparsification in Hypergraphs, Faster connectivity in low-rank hypergraphs via expander decomposition, Improving on best-of-many-Christofides for \(T\)-tours, Global and fixed-terminal cuts in digraphs, TBGMax: leveraging two-boundary graph pattern for lossless maximum-flow acceleration, Clique Cover and Graph Separation, Tracking paths, Partitioning subclasses of chordal graphs with few deletions, Unnamed Item, Minimum Cut and Minimum k -Cut in Hypergraphs via Branching Contractions, Two‐stage stochastic minimum s − t cut problems: Formulations, complexity and decomposition algorithms, A new approximation algorithm for the unbalanced min \(s\)-\(t\) cut problem, Strongly polynomial bounds for multiobjective and parametric global minimum cuts in graphs and hypergraphs, Partitioning subclasses of chordal graphs with few deletions, On size-constrained minimum \(s\mathrm{-}t\) cut problems and size-constrained dense subgraph problems, A new MILP formulation for the flying sidekick traveling salesman problem, Efficient Algorithms for the k Smallest Cuts Enumeration, Unnamed Item, Divide-and-conquer algorithms for partitioning hypergraphs and submodular systems, Shift of pairwise similarities for data clustering, Tight approximation ratio of a general greedy splitting algorithm for the minimum \(k\)-way cut problem, Faster cut sparsification of weighted graphs, Generating partitions of a graph into a fixed number of minimum weight cuts, Unnamed Item, Minimum label \(s\)-\(t\) cut has large integrality gaps, Complexity of the min-max (regret) versions of min cut problems, Certifying algorithms, Practical Minimum Cut Algorithms, Hypergraph \(k\)-cut in randomized polynomial time, LP Relaxation and Tree Packing for Minimum $k$-Cut, On the \(k\)-cut problem, Fast and Deterministic Approximations for k-Cut., Approximating \(k\)-cuts using network strength as a Lagrangean relaxation, Formulations and exact algorithms for the vehicle routing problem with time windows, Robust optimization in the presence of uncertainty: a generic approach, A new?old algorithm for minimum-cut and maximum-flow in closure graphs, Computing girth and cogirth in perturbed graphic matroids, Approximate \(\ell_0\)-penalized estimation of piecewise-constant signals on graphs, Computing finest mincut partitions of a graph and application to routing problems, A reactive GRASP with path relinking for capacitated clustering, Graph connectivity and its augmentation: Applications of MA orderings, Unnamed Item, Minimum Cuts of Simple Graphs in Almost Always Linear Time, Stochastic kronecker graphs, Unbalanced graph cuts with minimum capacity, Computing minimum multiway cuts in hypergraphs, Fixed parameter approximation scheme for min-max \(k\)-cut, Unnamed Item, A binomial approximation method for the Ising model, A new contraction technique with applications to congruency-constrained cuts, Fixed parameter approximation scheme for min-max \(k\)-cut, An exact combinatorial algorithm for minimum graph bisection, On cutting a few vertices from a graph, A General Framework for Graph Sparsification, Finding minimum 3-way cuts in hypergraphs, Beating the 2-approximation factor for global bicut, Random sampling and greedy sparsification for matroid optimization problems, An improved approximation algorithm of MULTIWAY CUT., Radiocoloring in planar graphs: Complexity and approximations, Randomized Approximation Schemes for Cuts and Flows in Capacitated Graphs, Fast Augmenting Paths by Random Sampling from Residual Graphs, Hypergraph k-Cut for Fixed k in Deterministic Polynomial Time, New approximations and hardness results for submodular partitioning problems
