LP Relaxation and Tree Packing for Minimum $k$-Cut
From MaRDI portal
Publication:3300759
DOI10.1137/19M1299359zbMath1444.05113arXiv1808.05765OpenAlexW3036281379MaRDI QIDQ3300759
Kent Quanrud, Chao Xu, Chandra Chekuri
Publication date: 30 July 2020
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1808.05765
Combinatorial optimization (90C27) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Connectivity (05C40)
Related Items (10)
Mean isoperimetry with control on outliers: exact and approximation algorithms ⋮ Partitioning subclasses of chordal graphs with few deletions ⋮ Partitioning subclasses of chordal graphs with few deletions ⋮ Minimum Violation Vertex Maps and Their Applications to Cut Problems ⋮ Hypergraph \(k\)-cut in randomized polynomial time ⋮ Unnamed Item ⋮ Fixed parameter approximation scheme for min-max \(k\)-cut ⋮ Fixed parameter approximation scheme for min-max \(k\)-cut ⋮ Unnamed Item ⋮ Hypergraph k-Cut for Fixed k in Deterministic Polynomial Time
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Minimum cost subpartitions in graphs
- A faster algorithm for computing the principal sequence of partitions of a graph
- Fully-dynamic min-cut
- The principal lattice of partitions of a submodular function
- A linear-time algorithm for finding a sparse \(k\)-connected spanning subgraph of a \(k\)-connected graph
- Packing algorithms for arborescences (and spanning trees) in capacitated graphs
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- On the \(k\)-cut problem
- Approximating \(k\)-cuts using network strength as a Lagrangean relaxation
- Deterministic Global Minimum Cut of a Simple Graph in Near-Linear Time
- Theory of Principal Partitions Revisited
- Optimal attack and reinforcement of a network
- A Polynomial Algorithm for the k-cut Problem for Fixed k
- Finding k Cuts within Twice the Optimal
- A new approach to the minimum cut problem
- A simple min-cut algorithm
- Near-Linear Time Approximation Schemes for some Implicit Fractional Packing Problems
- Local Flow Partitioning for Faster Edge Connectivity
- A General Approximation Technique for Constrained Forest Problems
- When Trees Collide: An Approximation Algorithm for the Generalized Steiner Problem on Networks
- Almost-polynomial ratio ETH-hardness of approximating densest k-subgraph
- Inapproximability of Maximum Edge Biclique, Maximum Balanced Biclique and Minimum k-Cut from the Small Set Expansion Hypothesis
- The number of minimum k -cuts: improving the Karger-Stein bound
- A Deterministic Algorithm for Finding All Minimum k‐Way Cuts
- The Steiner k-Cut Problem
- Minimum cuts in near-linear time
This page was built for publication: LP Relaxation and Tree Packing for Minimum $k$-Cut
