Fast and deterministic approximations for k-cut

Recommendations

Fast and Deterministic Approximations for k-Cut.
Polynomial-time approximation scheme for minimum \(k\)-cut in planar and minor-free graphs
Finding k Cuts within Twice the Optimal
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 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
Compact cactus representations of all non-trivial min-cuts
Computing Edge-Connectivity in Multigraphs and Capacitated Graphs
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
Fast and Deterministic Approximations for k-Cut.
Faster and Simpler Algorithms for Multicommodity Flow and Other Fractional Packing Problems
Finding k Cuts within Twice the Optimal
Graph expansion and the unique games conjecture
Inapproximability of maximum edge biclique, maximum balanced biclique and minimum \(k\)-cut from the small set expansion hypothesis
LP relaxation and tree packing for minimum \(k\)-cut
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
The Steiner k-Cut Problem
The minimum \(k\)-way cut of bounded size is fixed-parameter tractable
The multiplicative weights update method: a meta-algorithm and applications
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

(9)

scientific article; zbMATH DE number 7378605 (Why is no real title available?)
LP relaxation and tree packing for minimum \(k\)-cuts
Optimal Bounds for the k -cut Problem
scientific article; zbMATH DE number 18532 (Why is no real title available?)
A nearly 5/3-approximation FPT Algorithm for Min-k-Cut
scientific article; zbMATH DE number 1670649 (Why is no real title available?)
Approximation algorithms for minimum \(K\)-cut
scientific article; zbMATH DE number 6850403 (Why is no real title available?)
scientific article; zbMATH DE number 1066875 (Why is no real title available?)

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 Q5077149)