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

DOI10.1023/A:1009804919645zbMATH Open1028.90074OpenAlexW1529019776MaRDI QIDQ1583693FDOQ1583693

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

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

zbMATH Keywords

graphspolynomial algorithmminimum cuts\(k\)-way cuts

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35)

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
• A Faster Algorithm for Computing Minimum 5-Way and 6-Way Cuts in Graphs
• Combinatorial 5/6-approximation of Max Cut in graphs of maximum degree 3
• A Deterministic Algorithm for Finding All Minimum k‐Way Cuts
• Title not available (Why is that?)
• 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)