Approximation the minimum \(k\)-way cut in a graph via minimum 3-way cuts

DOI10.1023/A:1011620607786zbMath1135.05316OpenAlexW2104823067MaRDI QIDQ5952050

Liang Zhao, Hiroshi Nagamochi, Toshihide Ibaraki

Publication date: 8 January 2002

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1023/a:1011620607786

zbMATH Keywords

approximation algorithmedge weighted undirected graph

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Graph algorithms (graph-theoretic aspects) (05C85) Connectivity (05C40)

Related Items (8)

On generalized greedy splitting algorithms for multiway partition problems ⋮ Inapproximability of maximum biclique problems, minimum \( k\)-cut and densest at-least-\( k\)-subgraph from the small set expansion hypothesis ⋮ Minimum cost subpartitions in graphs ⋮ Efficient algorithms for the problems of enumerating cuts by non-decreasing weights ⋮ Partitioning subclasses of chordal graphs with few deletions ⋮ Tight approximation ratio of a general greedy splitting algorithm for the minimum \(k\)-way cut problem ⋮ Generating partitions of a graph into a fixed number of minimum weight cuts ⋮ Greedy splitting algorithms for approximating multiway partition problems

This page was built for publication: Approximation the minimum \(k\)-way cut in a graph via minimum 3-way cuts