Fast and Deterministic Approximations for k-Cut.
From MaRDI portal
Publication:5875475
DOI10.4230/LIPICS.APPROX-RANDOM.2019.23OpenAlexW2977612001MaRDI QIDQ5875475FDOQ5875475
Authors: Kent Quanrud 
Publication date: 3 February 2023
Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2019/11238/pdf/LIPIcs-APPROX-RANDOM-2019-23.pdf/
Cites Work
- Approximation algorithms for NP-hard problems.
- A data structure for dynamic trees
- Beyond the flow decomposition barrier
- On the Problem of Decomposing a Graph into n Connected Factors
- Edge-Disjoint Spanning Trees of Finite Graphs
- A General Approximation Technique for Constrained Forest Problems
- Title not available (Why is that?)
- Tree packing and approximating \(k\)-cuts
- Computing Edge-Connectivity in Multigraphs and Capacitated Graphs
- Cutting up is hard to do: the parameterised complexity of \(k\)-cut and related problems
- Title not available (Why is that?)
- Fast Algorithms for Finding Nearest Common Ancestors
- The minimum \(k\)-way cut of bounded size is fixed-parameter tractable
- Faster and Simpler Algorithms for Multicommodity Flow and Other Fractional Packing Problems
- A Faster Algorithm for Finding the Minimum Cut in a Directed Graph
- A new approach to the minimum cut problem
- A Polynomial Algorithm for the k-cut Problem for Fixed k
- Finding k Cuts within Twice the Optimal
- A simple min-cut algorithm
- Approximating \(k\)-cuts using network strength as a Lagrangean relaxation
- Minimum cuts in near-linear time
- Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity
- A linear-time algorithm for finding a sparse \(k\)-connected spanning subgraph of a \(k\)-connected graph
- Designing FPT algorithms for cut problems using randomized contractions
- Approximation algorithms for covering/packing integer programs
- Random sampling in cut, flow, and network design problems
- Title not available (Why is that?)
- Title not available (Why is that?)
- Tight approximation ratio of a general greedy splitting algorithm for the minimum \(k\)-way cut problem
- Approximability of capacitated network design
- Minimum cost subpartitions in graphs
- The Steiner k-Cut Problem
- On the \(k\)-cut problem
- An FPT algorithm beating 2-approximation for \(k\)-cut
- Local flow partitioning for faster edge connectivity
- Inapproximability of maximum edge biclique, maximum balanced biclique and minimum \(k\)-cut from the small set expansion hypothesis
- Randomized MWU for positive LPs
- Deterministic global minimum cut of a simple graph in near-linear time
- Near-linear time approximation schemes for some implicit fractional packing problems
- On approximating (sparse) covering integer programs
- The number of minimum \(k\)-cuts: improving the Karger-Stein bound
Cited In (11)
- Title not available (Why is that?)
- Optimal Bounds for the k -cut Problem
- Title not available (Why is that?)
- A nearly 5/3-approximation FPT Algorithm for Min-k-Cut
- Title not available (Why is that?)
- Title not available (Why is that?)
- Approximation algorithms for minimum \(K\)-cut
- Approximating submodular \(k\)-partition via principal partition sequence
- Title not available (Why is that?)
- Title not available (Why is that?)
- Hypergraph k-Cut for Fixed k in Deterministic Polynomial Time
This page was built for publication: Fast and Deterministic Approximations for k-Cut.
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5875475)
