Finding minimum 3-way cuts in hypergraphs

DOI10.1016/j.ipl.2010.05.003zbMath1233.05192OpenAlexW1981202693MaRDI QIDQ765477

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

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

Related Items (9)

Minimum Cuts and Sparsification in Hypergraphs ⋮ Global and fixed-terminal cuts in digraphs ⋮ Minimum Cut and Minimum k -Cut in Hypergraphs via Branching Contractions ⋮ Divide-and-conquer algorithms for partitioning hypergraphs and submodular systems ⋮ Hypergraph \(k\)-cut in randomized polynomial time ⋮ Submodular Cost Allocation Problem and Applications ⋮ Computing minimum multiway cuts in hypergraphs ⋮ Unnamed Item ⋮ Hypergraph k-Cut for Fixed k in Deterministic Polynomial Time

Cites Work

• Unnamed Item
• Unnamed Item
• A new and improved algorithm for the 3-cut problem
• A fast algorithm for computing minimum 3-way and 4-way cuts
• A fast hypergraph min-cut algorithm for circuit partitioning
• Finding Minimum 3-Way Cuts in Hypergraphs
• An Improved Divide-and-Conquer Algorithm for Finding All Minimum k-Way Cuts
• Divide-and-Conquer Algorithms for Partitioning Hypergraphs and Submodular Systems
• A new approach to the maximum-flow problem
• Multi-Terminal Network Flows
• Computing Edge-Connectivity in Multigraphs and Capacitated Graphs
• A Polynomial Algorithm for the k-cut Problem for Fixed k
• A new approach to the minimum cut problem
• A simple min-cut algorithm
• On minimum 3-cuts and approximating k-cuts using Cut Trees
• A Faster Algorithm for Computing Minimum 5-Way and 6-Way Cuts in Graphs
• A Deterministic Algorithm for Finding All Minimum k‐Way Cuts
• Cutsets and partitions of hypergraphs
• A divide-and-conquer approach to the minimum \(k\)-way cut problem.

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