Minimum Cut and Minimum k -Cut in Hypergraphs via Branching Contractions

DOI10.1145/3570162MaRDI QIDQ6075748

Fred Zhang, Debmalya Panigrahi, Kyle Fox

Publication date: 23 October 2023

Published in: ACM Transactions on Algorithms (Search for Journal in Brave)

zbMATH Keywords

minimum cut\(k\)-cuthypergraph connectivityhypergraph cut

Mathematics Subject Classification ID

Computer science (68-XX)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Finding minimum 3-way cuts in hypergraphs
• A linear-time algorithm for finding a sparse \(k\)-connected spanning subgraph of a \(k\)-connected graph
• Minimizing symmetric submodular functions
• Computing minimum multiway cuts in hypergraphs
• Faster connectivity in low-rank hypergraphs via expander decomposition
• A fast hypergraph min-cut algorithm for circuit partitioning
• Deterministic Global Minimum Cut of a Simple Graph in Near-Linear Time
• Sketching Cuts in Graphs and Hypergraphs
• An Improved Divide-and-Conquer Algorithm for Finding All Minimum k-Way Cuts
• 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
• Computing minimum cuts in hypergraphs
• Random Contractions and Sampling for Hypergraph and Hedge Connectivity
• The Karger-Stein algorithm is optimal for k-cut
• Parallelizing greedy for submodular set function maximization in matroids and beyond
• Minimum Cut and Minimum k-Cut in Hypergraphs via Branching Contractions
• A Deterministic Algorithm for Finding All Minimum k‐Way Cuts
• Minimum cuts in near-linear time
• Hypergraph k-Cut for Fixed k in Deterministic Polynomial Time
• A divide-and-conquer approach to the minimum \(k\)-way cut problem.

This page was built for publication: Minimum Cut and Minimum k -Cut in Hypergraphs via Branching Contractions