A Faster Algorithm for Computing Minimum 5-Way and 6-Way Cuts in Graphs

DOI10.1007/3-540-48686-0_16zbMath0938.05057OpenAlexW1562526251MaRDI QIDQ4938664

Hiroshi Nagamochi, Toshihide Ibaraki, Shigeki Katayama

Publication date: 23 February 2000

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/3-540-48686-0_16

zbMATH Keywords

partitionmaximum flowdeterministic algorithmminimum \(k\)-way cut problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (2)

Tight approximation ratio of a general greedy splitting algorithm for the minimum \(k\)-way cut problem ⋮ Finding minimum 3-way cuts in hypergraphs

This page was built for publication: A Faster Algorithm for Computing Minimum 5-Way and 6-Way Cuts in Graphs