Minimum Cuts and Sparsification in Hypergraphs
From MaRDI portal
Publication:4561257
DOI10.1137/18M1163865zbMath1409.90156OpenAlexW2903204436WikidataQ128869027 ScholiaQ128869027MaRDI QIDQ4561257
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
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