Tight approximation ratio of a general greedy splitting algorithm for the minimum \(k\)-way cut problem

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

zbMATH Keywords

approximation algorithm\(k\)-way cut

Mathematics Subject Classification ID

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