Tight Approximation Ratio of a General Greedy Splitting Algorithm for the Minimum k-Way Cut Problem
- 8 May 2009
- journal article
- Published by Springer Nature in Algorithmica
- Vol. 59 (4) , 510-520
Abstract
No abstract availableKeywords
All Related Versions
This publication has 11 references indexed in Scilit:
- Greedy splitting algorithms for approximating multiway partition problemsMathematical Programming, 2004
- On the complexity of the extended euclidean algorithm (Extended Abstract)Electronic Notes in Theoretical Computer Science, 2003
- Approximating the Minimum k-way Cut in a Graph via Minimum 3-way CutsJournal of Combinatorial Optimization, 2001
- A fast algorithm for computing minimum 3-way and 4-way cutsMathematical Programming, 2000
- A Faster Algorithm for Computing Minimum 5-Way and 6-Way Cuts in GraphsLecture Notes in Computer Science, 1999
- A new and improved algorithm for the 3-cut problemOperations Research Letters, 1997
- On minimum 3-cuts and approximating k-cuts using Cut Trees1996
- Finding k Cuts within Twice the OptimalSIAM Journal on Computing, 1995
- A Polynomial Algorithm for the k-cut Problem for Fixed kMathematics of Operations Research, 1994
- Computing Edge-Connectivity in Multigraphs and Capacitated GraphsSIAM Journal on Discrete Mathematics, 1992