Finding minimum 3-way cuts in hypergraphs

DOI10.1016/J.IPL.2010.05.003MaRDI QIDQ765477zbMATH OpenOpenAlexFDO

Authors Mingyu Xiao

Publication date 19 March 2012

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ipl.2010.05.003

zbMATH Keywords

graph algorithms\(k\)-way cutedge-weighted hypergraphminimum 3-way cut problem

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Signed and weighted graphs (05C22) Connectivity (05C40) Hypergraphs (05C65)

Recommendations

• Finding Minimum 3-Way Cuts in Hypergraphs
• Computing minimum multiway cuts in hypergraphs
• Computing minimum multiway cuts in hypergraphs from hypertree packings
• scientific article; zbMATH DE number 1342143
• A fast algorithm for computing minimum 3-way and 4-way cuts

Cites work

• scientific article; zbMATH DE number 5485527 (Why is no real title available?)
• scientific article; zbMATH DE number 1445372 (Why is no real title available?)
• A Deterministic Algorithm for Finding All Minimum k‐Way Cuts
• A Faster Algorithm for Computing Minimum 5-Way and 6-Way Cuts in Graphs
• A Polynomial Algorithm for the k-cut Problem for Fixed k
• A divide-and-conquer approach to the minimum \(k\)-way cut problem.
• A fast algorithm for computing minimum 3-way and 4-way cuts
• A fast hypergraph min-cut algorithm for circuit partitioning
• A new and improved algorithm for the 3-cut problem
• A new approach to the maximum-flow problem
• A new approach to the minimum cut problem
• A simple min-cut algorithm
• An Improved Divide-and-Conquer Algorithm for Finding All Minimum k-Way Cuts
• Computing Edge-Connectivity in Multigraphs and Capacitated Graphs
• Cutsets and partitions of hypergraphs
• Divide-and-conquer algorithms for partitioning hypergraphs and submodular systems
• Finding Minimum 3-Way Cuts in Hypergraphs
• Multi-Terminal Network Flows
• On minimum 3-cuts and approximating k-cuts using cut trees

Cited in

(16)

• Minimum cuts and sparsification in hypergraphs
• On the hardness of approximating the \(k\)-\textsc{Way Hypergraph Cut} problem
• Hypergraph \(k\)-cut in randomized polynomial time
• Finding Minimum 3-Way Cuts in Hypergraphs
• A polynomial time algorithm for finding a minimum 4-partition of a submodular function
• Deterministic enumeration of all minimum cut-sets and k-cut-sets in hypergraphs for fixed k
• Minimum s-t hypercut in (s, t)-planar hypergraphs
• Global and fixed-terminal cuts in digraphs
• Minimum Cut and Minimum k -Cut in Hypergraphs via Branching Contractions
• Modeling hypergraphs by graphs with the same mincut properties
• Computing minimum multiway cuts in hypergraphs
• Computing minimum multiway cuts in hypergraphs from hypertree packings
• Submodular Cost Allocation Problem and Applications
• On minimal cuts of recursively generated hypergraphs
• Divide-and-conquer algorithms for partitioning hypergraphs and submodular systems
• Hypergraph k-Cut for Fixed k in Deterministic Polynomial Time

This page was built for publication: Finding minimum 3-way cuts in hypergraphs

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