A fast algorithm for computing minimum 3-way and 4-way cuts

DOI10.1007/S101070000183MaRDI QIDQ1587938zbMATH OpenFDO

Authors Hiroshi Nagamochi, Toshihide Ibaraki

Publication date 28 February 2001

Published in Mathematical Programming. Series A. Series B (Search for Journal in Brave)

zbMATH Keywords

minimum cutsubmodular functionpolynomial algorithm

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• scientific article; zbMATH DE number 1342143
• scientific article; zbMATH DE number 1372653
• A divide-and-conquer approach to the minimum \(k\)-way cut problem.
• Publication:4952694
• A new and improved algorithm for the 3-cut problem

Cited in

(8)

• Efficient algorithms for the problems of enumerating cuts by non-decreasing weights
• A polynomial time algorithm for finding a minimum 4-partition of a submodular function
• Generating partitions of a graph into a fixed number of minimum weight cuts
• A simple and fast min-cut algorithm
• Finding minimum 3-way cuts in hypergraphs
• Efficient Algorithms for the k Smallest Cuts Enumeration
• Tight approximation ratio of a general greedy splitting algorithm for the minimum \(k\)-way cut problem
• On generalized greedy splitting algorithms for multiway partition problems

This page was built for publication: A fast algorithm for computing minimum 3-way and 4-way cuts

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