Tight approximation ratio of a general greedy splitting algorithm for the minimum k-way cut problem
DOI10.1007/S00453-009-9316-1zbMATH Open1211.68515OpenAlexW2125472409MaRDI QIDQ633844FDOQ633844
Authors: Mingyu Xiao, Leizhen Cai, Andrew Chi-Chih Yao 
Publication date: 30 March 2011
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-009-9316-1
Recommendations
- Approximation the minimum \(k\)-way cut in a graph via minimum 3-way cuts
- scientific article; zbMATH DE number 1522944
- A divide-and-conquer approach to the minimum \(k\)-way cut problem.
- An Improved Divide-and-Conquer Algorithm for Finding All Minimum k-Way Cuts
- On minimum 3-cuts and approximating k-cuts using cut trees
Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms (68W40) Approximation algorithms (68W25) Signed and weighted graphs (05C22)
Cites Work
- Tree packing and approximating \(k\)-cuts
- Computing Edge-Connectivity in Multigraphs and Capacitated Graphs
- 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 new and improved algorithm for the 3-cut problem
- Title not available (Why is that?)
- Greedy splitting algorithms for approximating multiway partition problems
- A fast algorithm for computing minimum 3-way and 4-way cuts
- On generalized greedy splitting algorithms for multiway partition problems
- Title not available (Why is that?)
- Title not available (Why is that?)
- A Faster Algorithm for Computing Minimum 5-Way and 6-Way Cuts in Graphs
- Title not available (Why is that?)
- Approximation the minimum \(k\)-way cut in a graph via minimum 3-way cuts
Cited In (5)
- Partitioning subclasses of chordal graphs with few deletions
- Inapproximability of maximum biclique problems, minimum \( k\)-cut and densest at-least-\( k\)-subgraph from the small set expansion hypothesis
- Title not available (Why is that?)
- Fast and Deterministic Approximations for k-Cut.
- New algorithms for a simple measure of network partitioning
This page was built for publication: Tight approximation ratio of a general greedy splitting algorithm for the minimum \(k\)-way cut problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q633844)
