Tight approximation ratio of a general greedy splitting algorithm for the minimum \(k\)-way cut problem
type: Item
instance of: scholarly article
title: Tight approximation ratio of a general greedy splitting algorithm for the minimum \(k\)-way cut problem
zbMATH Open document ID: 1211.68515
author: Mingyu Xiao
author: Leizhen Cai
author: Andrew Chi-Chih Yao
published in: Algorithmica
publication date: 2011-03-30T00:00:00Z
Mathematics Subject Classification ID: 68W25
Mathematics Subject Classification ID: 05C22
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 68W40
zbMATH DE Number: 5871669
zbMATH Keywords: \(k\)-way cut
zbMATH Keywords: approximation algorithm
MaRDI profile type: Publication
full work available at URL: s00453-009-9316-1
OpenAlex ID: W2125472409
cites work: A Polynomial Algorithm for the k-cut Problem for Fixed k
cites work: Q3549696
cites work: A new approach to the minimum cut problem
cites work: Q4763403
cites work: Computing Edge-Connectivity in Multigraphs and Capacitated Graphs
cites work: A new and improved algorithm for the 3-cut problem
cites work: A fast algorithm for computing minimum 3-way and 4-way cuts
cites work: A Faster Algorithm for Computing Minimum 5-Way and 6-Way Cuts in Graphs
cites work: Q4952694
cites work: Finding k Cuts within Twice the Optimal
cites work: Tree packing and approximating \(k\)-cuts
cites work: Q4828991
cites work: Approximation the minimum \(k\)-way cut in a graph via minimum 3-way cuts
cites work: Greedy splitting algorithms for approximating multiway partition problems
cites work: On generalized greedy splitting algorithms for multiway partition problems
DOI: 10.1007/S00453-009-9316-1
description: scientific article; zbMATH DE number 5871669