Fast and Deterministic Approximations for k-Cut.
From MaRDI portal
Publication:5875475
Recommendations
- Fast and deterministic approximations for \(k\)-cut
- Finding k Cuts within Twice the Optimal
- Polynomial-time approximation scheme for minimum \(k\)-cut in planar and minor-free graphs
- Hypergraph k-Cut for Fixed k in Deterministic Polynomial Time
- A Polynomial Algorithm for the k-cut Problem for Fixed k
Cites work
- scientific article; zbMATH DE number 437577 (Why is no real title available?)
- scientific article; zbMATH DE number 5485527 (Why is no real title available?)
- scientific article; zbMATH DE number 1445293 (Why is no real title available?)
- scientific article; zbMATH DE number 1445372 (Why is no real title available?)
- A Faster Algorithm for Finding the Minimum Cut in a Directed Graph
- A General Approximation Technique for Constrained Forest Problems
- A Polynomial Algorithm for the k-cut Problem for Fixed k
- A data structure for dynamic trees
- A linear-time algorithm for finding a sparse \(k\)-connected spanning subgraph of a \(k\)-connected graph
- A new approach to the minimum cut problem
- A simple min-cut algorithm
- An FPT algorithm beating 2-approximation for \(k\)-cut
- Approximability of capacitated network design
- Approximating \(k\)-cuts using network strength as a Lagrangean relaxation
- Approximation algorithms for NP-hard problems.
- Approximation algorithms for covering/packing integer programs
- Beyond the flow decomposition barrier
- Computing Edge-Connectivity in Multigraphs and Capacitated Graphs
- Cutting up is hard to do: the parameterised complexity of \(k\)-cut and related problems
- Designing FPT algorithms for cut problems using randomized contractions
- Deterministic global minimum cut of a simple graph in near-linear time
- Edge-Disjoint Spanning Trees of Finite Graphs
- Fast Algorithms for Finding Nearest Common Ancestors
- Faster and Simpler Algorithms for Multicommodity Flow and Other Fractional Packing Problems
- Finding k Cuts within Twice the Optimal
- Inapproximability of maximum edge biclique, maximum balanced biclique and minimum \(k\)-cut from the small set expansion hypothesis
- Local flow partitioning for faster edge connectivity
- Minimum cost subpartitions in graphs
- Minimum cuts in near-linear time
- Near-linear time approximation schemes for some implicit fractional packing problems
- On approximating (sparse) covering integer programs
- On the Problem of Decomposing a Graph into n Connected Factors
- On the \(k\)-cut problem
- Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity
- Random sampling in cut, flow, and network design problems
- Randomized MWU for positive LPs
- The Steiner k-Cut Problem
- The minimum \(k\)-way cut of bounded size is fixed-parameter tractable
- The number of minimum \(k\)-cuts: improving the Karger-Stein bound
- Tight approximation ratio of a general greedy splitting algorithm for the minimum \(k\)-way cut problem
- Tree packing and approximating \(k\)-cuts
Cited in
(12)- Optimal Bounds for the k -cut Problem
- A nearly 5/3-approximation FPT Algorithm for Min-k-Cut
- Approximating submodular \(k\)-partition via principal partition sequence
- scientific article; zbMATH DE number 6850403 (Why is no real title available?)
- scientific article; zbMATH DE number 1670649 (Why is no real title available?)
- LP relaxation and tree packing for minimum \(k\)-cuts
- Approximation algorithms for minimum \(K\)-cut
- scientific article; zbMATH DE number 18532 (Why is no real title available?)
- Fast and deterministic approximations for \(k\)-cut
- scientific article; zbMATH DE number 1066875 (Why is no real title available?)
- scientific article; zbMATH DE number 7378605 (Why is no real title available?)
- 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)
