Fast and Deterministic Approximations for k-Cut.
From MaRDI portal
Publication:5875475
DOI10.4230/LIPICS.APPROX-RANDOM.2019.23OpenAlexW2977612001MaRDI QIDQ5875475FDOQ5875475
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
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- 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
- 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
- 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
- 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
- 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
- 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)
