Hypergraph k-Cut for Fixed k in Deterministic Polynomial Time
From MaRDI portal
Publication:5870380
DOI10.1287/moor.2021.1250OpenAlexW3089158720MaRDI QIDQ5870380
Chandra Chekuri, Karthekeyan Chandrasekaran
Publication date: 9 January 2023
Published in: Mathematics of Operations Research (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2009.12442
Related Items (1)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Finding minimum 3-way cuts in hypergraphs
- Parameterized graph separation problems
- A linear-time algorithm for finding a sparse \(k\)-connected spanning subgraph of a \(k\)-connected graph
- Greedy splitting algorithms for approximating multiway partition problems
- Computing minimum multiway cuts in hypergraphs
- Hypergraph \(k\)-cut in randomized polynomial time
- A simple algorithm for the multiway cut problem
- Divide-and-conquer algorithms for partitioning hypergraphs and submodular systems
- Inapproximability of maximum biclique problems, minimum \( k\)-cut and densest at-least-\( k\)-subgraph from the small set expansion hypothesis
- Graph expansion and the unique games conjecture
- LP Relaxation and Tree Packing for Minimum $k$-Cut
- A Polynomial Algorithm for the k-cut Problem for Fixed k
- The Complexity of Multiterminal Cuts
- Finding k Cuts within Twice the Optimal
- A new approach to the minimum cut problem
- A simple min-cut algorithm
- Minimum Cuts and Sparsification in Hypergraphs
- Random Contractions and Sampling for Hypergraph and Hedge Connectivity
- Almost-polynomial ratio ETH-hardness of approximating densest k-subgraph
- The Karger-Stein algorithm is optimal for k-cut
- A nearly 5/3-approximation FPT Algorithm for Min-k-Cut
- Minimum Cut and Minimum k-Cut in Hypergraphs via Branching Contractions
- A Deterministic Algorithm for Finding All Minimum k‐Way Cuts
- The Minimum k-way Cut of Bounded Size is Fixed-Parameter Tractable
- Approximation Algorithms for Submodular Multiway Partition
- Cutsets and partitions of hypergraphs
- Local Distribution and the Symmetry Gap: Approximability of Multiway Partitioning Problems
- Fast and Deterministic Approximations for k-Cut.
- Fixed parameter approximation scheme for min-max \(k\)-cut
This page was built for publication: Hypergraph k-Cut for Fixed k in Deterministic Polynomial Time
