On generalized greedy splitting algorithms for multiway partition problems

DOI10.1016/j.dam.2003.10.007zbMath1103.68145OpenAlexW2056463115MaRDI QIDQ1887049

Toshihide Ibaraki, Liang Zhao, Hiroshi Nagamochi

Publication date: 23 November 2004

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2003.10.007

zbMATH Keywords

Approximation algorithmSubmodular function\(k\)-way cutMultiterminal cutMultiway partition problem

Mathematics Subject Classification ID

Partitions of sets (05A18) Approximation algorithms (68W25)

Related Items (2)

On generalized greedy splitting algorithms for multiway partition problems ⋮ Tight approximation ratio of a general greedy splitting algorithm for the minimum \(k\)-way cut problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A new and improved algorithm for the 3-cut problem
• Minimizing symmetric submodular functions
• Partitions and network reliability
• A faster algorithm for computing minimum 5-way and 6-way cuts in graphs
• A fast algorithm for computing minimum 3-way and 4-way cuts
• On generalized greedy splitting algorithms for multiway partition problems
• Rounding algorithms for a geometric embedding of minimum multiway cut
• Multiprocessor Scheduling with the Aid of Network Flow Algorithms
• A Polynomial Algorithm for the k-cut Problem for Fixed k
• The Complexity of Multiterminal Cuts
• Finding k Cuts within Twice the Optimal
• Multiway cuts in directed and node weighted graphs
• On minimum 3-cuts and approximating k-cuts using Cut Trees
• Cutsets and partitions of hypergraphs
• Approximation the minimum \(k\)-way cut in a graph via minimum 3-way cuts

This page was built for publication: On generalized greedy splitting algorithms for multiway partition problems