An Improved Divide-and-Conquer Algorithm for Finding All Minimum k-Way Cuts

DOI10.1007/978-3-540-92182-0_21MaRDI QIDQ3596719zbMATH OpenOpenAlexFDO

Authors Mingyu Xiao

Publication date 29 January 2009

Published in Algorithms and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-92182-0_21

zbMATH Keywords

\(k\)-way cutdivide-and-conquergraph algorithm

Mathematics Subject Classification ID

Connectivity (05C40) Graph algorithms (graph-theoretic aspects) (05C85) Programming involving graphs or networks (90C35)

Recommendations

• A Deterministic Algorithm for Finding All Minimum k‐Way Cuts
• scientific article; zbMATH DE number 1372653
• A divide-and-conquer approach to the minimum \(k\)-way cut problem.
• Approximation the minimum \(k\)-way cut in a graph via minimum 3-way cuts
• scientific article; zbMATH DE number 1522944

Cited in

(14)

• Computing minimum multiway cuts in hypergraphs
• Hypergraph \(k\)-cut in randomized polynomial time
• Divide-and-conquer algorithms for partitioning hypergraphs and submodular systems
• scientific article; zbMATH DE number 1372653 (Why is no real title available?)
• The number of minimum k-cuts: improving the Karger-Stein bound
• A Deterministic Algorithm for Finding All Minimum k‐Way Cuts
• A divide-and-conquer approach to the minimum \(k\)-way cut problem.
• Minimum Cut and Minimum k -Cut in Hypergraphs via Branching Contractions
• Tight approximation ratio of a general greedy splitting algorithm for the minimum \(k\)-way cut problem
• Deterministic enumeration of all minimum cut-sets and k-cut-sets in hypergraphs for fixed k
• A polynomial time algorithm for finding a minimum 4-partition of a submodular function
• Finding minimum 3-way cuts in hypergraphs
• Minimum cost subpartitions in graphs
• Simple and improved parameterized algorithms for multiterminal cuts

This page was built for publication: An Improved Divide-and-Conquer Algorithm for Finding All Minimum k-Way Cuts

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