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

DOI10.1007/3-540-48686-0_16MaRDI QIDQ4938664zbMATH OpenOpenAlexFDO

Authors Hiroshi Nagamochi, Shigeki Katayama, Toshihide Ibaraki

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

deterministic algorithmmaximum flowminimum \(k\)-way cut problempartition

Mathematics Subject Classification ID

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

Recommendations

• A faster algorithm for computing minimum 5-way and 6-way cuts in graphs
• Publication:4952694
• A Deterministic Algorithm for Finding All Minimum k‐Way Cuts
• scientific article; zbMATH DE number 1342143
• scientific article; zbMATH DE number 1372653

Cited in

(5)

• Combinatorial 5/6-approximation of Max Cut in graphs of maximum degree 3
• A faster algorithm for computing minimum 5-way and 6-way cuts in graphs
• scientific article; zbMATH DE number 1445372 (Why is no real title available?)
• 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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4938664)