Deterministic enumeration of all minimum cut-sets and k-cut-sets in hypergraphs for fixed k

DOI10.1007/S10107-023-02013-8MaRDI QIDQ6608037FDOQ6608037

Authors: Calvin Beideman, Karthekeyan Chandrasekaran, Weihang Wang 

Publication date: 19 September 2024

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Recommendations

• Hypergraph k-Cut for Fixed k in Deterministic Polynomial Time
• Minimum cut and minimum \(k\)-cut in hypergraphs via branching contractions
• Hypergraph \(k\)-cut in randomized polynomial time
• Computing minimum multiway cuts in hypergraphs

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Combinatorial optimization (90C27) Hypergraphs (05C65)

Cites Work

• Algorithmic Aspects of Graph Connectivity
• The Complexity of Multiterminal Cuts
• A Combinatorial Decomposition Theory
• Title not available (Why is that?)
• Canonical decompositions of symmetric submodular systems
• A new approach to the minimum cut problem
• Computing All Small Cuts in an Undirected Network
• A Polynomial Algorithm for the k-cut Problem for Fixed k
• Finding k Cuts within Twice the Optimal
• Title not available (Why is that?)
• Approximating \(k\)-cuts using network strength as a Lagrangean relaxation
• Minimum cuts in near-linear time
• Decomposition of submodular functions
• Minimizing submodular functions over families of sets
• Edge-augmentation of hypergraphs
• Greedy splitting algorithms for approximating multiway partition problems
• Title not available (Why is that?)
• An Improved Divide-and-Conquer Algorithm for Finding All Minimum k-Way Cuts
• A Deterministic Algorithm for Finding All Minimum k‐Way Cuts
• Cutsets and partitions of hypergraphs
• Finding minimum 3-way cuts in hypergraphs
• Hypergraph \(k\)-cut in randomized polynomial time
• Minimum cuts and sparsification in hypergraphs
• Hypergraph k-Cut for Fixed k in Deterministic Polynomial Time
• On the number of small cut in a graph
• Suboptimal cuts: their enumeration, weight and number (extended abstract)
• Strongly polynomial bounds for multiobjective and parametric global minimum cuts in graphs and hypergraphs
• LP relaxation and tree packing for minimum \(k\)-cut
• An FPT algorithm beating 2-approximation for \(k\)-cut
• Inapproximability of maximum biclique problems, minimum \( k\)-cut and densest at-least-\( k\)-subgraph from the small set expansion hypothesis
• Computing minimum multiway cuts in hypergraphs
• Divide-and-conquer algorithms for partitioning hypergraphs and submodular systems
• Random contractions and sampling for hypergraph and hedge connectivity
• Minimum cut and minimum \(k\)-cut in hypergraphs via branching contractions
• The number of minimum \(k\)-cuts: improving the Karger-Stein bound
• The Karger-Stein algorithm is optimal for k-cut
• Title not available (Why is that?)
• Counting and enumerating optimum cut sets for hypergraph \(k\)-partitioning problems for fixed \(k\)

This page was built for publication: Deterministic enumeration of all minimum cut-sets and \(k\)-cut-sets in hypergraphs for fixed \(k\)

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