Tight approximation ratio of a general greedy splitting algorithm for the minimum \(k\)-way cut problem
From MaRDI portal
Publication:633844
DOI10.1007/s00453-009-9316-1zbMath1211.68515OpenAlexW2125472409MaRDI QIDQ633844
Mingyu Xiao, Andrew Chi-Chih Yao, Leizhen Cai
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
Analysis of algorithms (68W40) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Signed and weighted graphs (05C22)
Related Items
Inapproximability of maximum biclique problems, minimum \( k\)-cut and densest at-least-\( k\)-subgraph from the small set expansion hypothesis, Partitioning subclasses of chordal graphs with few deletions, New algorithms for a simple measure of network partitioning, Fast and Deterministic Approximations for k-Cut., Unnamed Item
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A new and improved algorithm for the 3-cut problem
- A fast algorithm for computing minimum 3-way and 4-way cuts
- Greedy splitting algorithms for approximating multiway partition problems
- On generalized greedy splitting algorithms for multiway partition problems
- Computing Edge-Connectivity in Multigraphs and Capacitated Graphs
- 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 Faster Algorithm for Computing Minimum 5-Way and 6-Way Cuts in Graphs
- Approximation the minimum \(k\)-way cut in a graph via minimum 3-way cuts