Minimum Cuts and Sparsification in Hypergraphs

DOI10.1137/18M1163865zbMath1409.90156OpenAlexW2903204436WikidataQ128869027 ScholiaQ128869027MaRDI QIDQ4561257

Chandra Chekuri, Chao Xu

Publication date: 5 December 2018

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/18m1163865

zbMATH Keywords

hypergraphminimum cutsparsificationcactus

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Hypergraphs (05C65) Combinatorial optimization (90C27)

Related Items (5)

Faster connectivity in low-rank hypergraphs via expander decomposition ⋮ Submodular reassignment problem for reallocating agents to tasks with synergy effects ⋮ Multicriteria cuts and size-constrained \(k\)-cuts in hypergraphs ⋮ Multicriteria Cuts and Size-Constrained k-Cuts in Hypergraphs. ⋮ Hypergraph k-Cut for Fixed k in Deterministic Polynomial Time

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the shortest spanning subtree of a graph and the traveling salesman problem
• Realizing symmetric set functions as hypergraph cut capacity
• Canonical decompositions of symmetric submodular systems
• Finding minimum 3-way cuts in hypergraphs
• Strongly polynomial bounds for multiobjective and parametric global minimum cuts in graphs and hypergraphs
• Decomposition of submodular functions
• Computing on a free tree via complexity-preserving mappings
• A linear-time algorithm for finding a sparse \(k\)-connected spanning subgraph of a \(k\)-connected graph
• Minimizing symmetric submodular functions
• Edge-augmentation of hypergraphs
• Coverings and structure of crossing families
• On decomposing a hypergraph into \(k\) connected sub-hypergraphs
• A correctness certificate for the Stoer-Wagner min-cut algorithm
• Computing minimum multiway cuts in hypergraphs
• A data structure for dynamic trees
• A paradigm for listing \((s,t)\)-cuts in graphs
• 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
• Algorithmic Aspects of Graph Connectivity
• A Combinatorial Decomposition Theory
• Computing Edge-Connectivity in Multigraphs and Capacitated Graphs
• On sparse subgraphs preserving connectivity properties
• A Polynomial Algorithm for the k-cut Problem for Fixed k
• Finding k Cuts within Twice the Optimal
• 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
• Local Flow Partitioning for Faster Edge Connectivity
• Twice-Ramanujan Sparsifiers
• Building Chain and Cactus Representations of All Minimum Cuts from Hao–Orlin in the Same Asymptotic Run Time
• The Minset-Poset Approach to Representations of Graph Connectivity
• An SDP-based algorithm for linear-sized spectral sparsification
• Randomized Approximation Schemes for Cuts and Flows in Capacitated Graphs
• A general framework for graph sparsification
• Minimum cuts in near-linear time
• Max flows in O(nm) time, or better
• Cutsets and partitions of hypergraphs
• On minimizing symmetric set functions

This page was built for publication: Minimum Cuts and Sparsification in Hypergraphs