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)

Full work available at URL https://doi.org/10.1007/S101070000183

zbMATH Keywords

minimum cutpolynomial algorithmsubmodular function

Mathematics Subject Classification ID

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

Review text

The authors present a new polynomial algorithm for computing minimum 3-way and 4-way cuts in an edge-weighted graph. The algorithm is extended to the problem of finding a minimum 3-way cut in a symmetric submodular system.

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

(10)

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

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)