A faster algorithm for computing minimum 5-way and 6-way cuts in graphs

DOI10.1023/A:1009804919645MaRDI QIDQ1583693zbMATH OpenOpenAlexFDO

Authors Hiroshi Nagamochi, Shigeki Katayama, Toshihide Ibaraki

Publication date 30 October 2000

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

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

zbMATH Keywords

graphspolynomial algorithmminimum cuts\(k\)-way cuts

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35)

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

(9)

• 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
• 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
• A Deterministic Algorithm for Finding All Minimum k‐Way Cuts
• scientific article; zbMATH DE number 1445372 (Why is no real title available?)
• Efficient Algorithms for the k Smallest Cuts Enumeration
• On generalized greedy splitting algorithms for multiway partition problems

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 Q1583693)