Minimum cuts in near-linear time
From MaRDI portal
Publication:5487825
DOI10.1145/331605.331608zbMath1094.68613OpenAlexW1964510837MaRDI QIDQ5487825
Publication date: 12 September 2006
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.651.2363
Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20)
Related Items (40)
Quantum Speedup for Graph Sparsification, Cut Approximation, and Laplacian Solving ⋮ Minimum Cuts in Surface Graphs ⋮ Cache Oblivious Minimum Cut ⋮ Faster Algorithms for Next Breakpoint and Max Value for Parametric Global Minimum Cuts ⋮ Minimum degree orderings ⋮ Efficient algorithms for the problems of enumerating cuts by non-decreasing weights ⋮ Designing FPT Algorithms for Cut Problems Using Randomized Contractions ⋮ Computing Weighted Strength and Applications to Partitioning ⋮ Minimum Cuts and Sparsification in Hypergraphs ⋮ Faster connectivity in low-rank hypergraphs via expander decomposition ⋮ Improving on best-of-many-Christofides for \(T\)-tours ⋮ \textsc{FlipCut} supertrees: towards matrix representation accuracy in polynomial time ⋮ TBGMax: leveraging two-boundary graph pattern for lossless maximum-flow acceleration ⋮ A note on the polytope of bipartite TSP ⋮ A combinatorial cut-toggling algorithm for solving Laplacian linear systems ⋮ Minimum Cut and Minimum k -Cut in Hypergraphs via Branching Contractions ⋮ Time-optimal construction of overlay networks ⋮ Strongly polynomial bounds for multiobjective and parametric global minimum cuts in graphs and hypergraphs ⋮ Unnamed Item ⋮ Efficient Algorithms for the k Smallest Cuts Enumeration ⋮ Unnamed Item ⋮ Generalized cut trees for edge-connectivity ⋮ The reverse selective balance center location problem on trees ⋮ Minimum Cuts and Shortest Cycles in Directed Planar Graphs via Noncrossing Shortest Paths ⋮ Practical Minimum Cut Algorithms ⋮ Fast approximation of matroid packing and covering ⋮ 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 ⋮ Certifying 3-edge-connectivity ⋮ Ranking and Sparsifying a Connection Graph ⋮ Evolutionary Network Analysis ⋮ Unnamed Item ⋮ Local Flow Partitioning for Faster Edge Connectivity ⋮ Connectivity interdiction ⋮ Randomized Approximation Schemes for Cuts and Flows in Capacitated Graphs ⋮ I/O efficient algorithms for the minimum cut problem on unweighted undirected graphs ⋮ Unnamed Item
This page was built for publication: Minimum cuts in near-linear time
