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

DOI10.1007/S00453-009-9316-1MaRDI QIDQ633844zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

approximation algorithm\(k\)-way cut

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms (68W40) Approximation algorithms (68W25) Signed and weighted graphs (05C22)

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

Cites work

• scientific article; zbMATH DE number 5485527 (Why is no real title available?)
• scientific article; zbMATH DE number 742961 (Why is no real title available?)
• scientific article; zbMATH DE number 2119718 (Why is no real title available?)
• scientific article; zbMATH DE number 1445372 (Why is no real title available?)
• A Faster Algorithm for Computing Minimum 5-Way and 6-Way Cuts in Graphs
• A Polynomial Algorithm for the k-cut Problem for Fixed k
• A fast algorithm for computing minimum 3-way and 4-way cuts
• A new and improved algorithm for the 3-cut problem
• A new approach to the minimum cut problem
• Approximation the minimum \(k\)-way cut in a graph via minimum 3-way cuts
• Computing Edge-Connectivity in Multigraphs and Capacitated Graphs
• Finding k Cuts within Twice the Optimal
• Greedy splitting algorithms for approximating multiway partition problems
• On generalized greedy splitting algorithms for multiway partition problems
• Tree packing and approximating \(k\)-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
• Fast and Deterministic Approximations for k-Cut.
• New algorithms for a simple measure of network partitioning
• Fast and deterministic approximations for \(k\)-cut

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)