Minimum cuts and sparsification in hypergraphs
From MaRDI portal
Recommendations
Cites work
- A Combinatorial Decomposition Theory
- A correctness certificate for the Stoer-Wagner min-cut algorithm
- A data structure for dynamic trees
- A fast hypergraph min-cut algorithm for circuit partitioning
- A general framework for graph sparsification
- A linear-time algorithm for finding a sparse \(k\)-connected spanning subgraph of a \(k\)-connected graph
- A near-linear time algorithm for constructing a cactus representation of minimum cuts
- A new approach to the minimum cut problem
- A paradigm for listing \((s,t)\)-cuts in graphs
- A Polynomial Algorithm for the k-cut Problem for Fixed k
- A simple min-cut algorithm
- Algorithmic Aspects of Graph Connectivity
- An SDP-based algorithm for linear-sized spectral sparsification
- Building Chain and Cactus Representations of All Minimum Cuts from Hao–Orlin in the Same Asymptotic Run Time
- Canonical decompositions of symmetric submodular systems
- Computing Edge-Connectivity in Multigraphs and Capacitated Graphs
- Computing minimum cuts in hypergraphs
- Computing minimum multiway cuts in hypergraphs
- Computing on a free tree via complexity-preserving mappings
- Connections in combinatorial optimization
- Coverings and structure of crossing families
- Cutsets and partitions of hypergraphs
- Decomposition of submodular functions
- Deterministic global minimum cut of a simple graph in near-linear time
- Edge-augmentation of hypergraphs
- Finding k Cuts within Twice the Optimal
- Finding minimum 3-way cuts in hypergraphs
- scientific article; zbMATH DE number 437577 (Why is no real title available?)
- scientific article; zbMATH DE number 5485527 (Why is no real title available?)
- scientific article; zbMATH DE number 6850403 (Why is no real title available?)
- scientific article; zbMATH DE number 3349645 (Why is no real title available?)
- Local flow partitioning for faster edge connectivity
- Max flows in O(nm) time, or better
- Minimizing symmetric submodular functions
- Minimum cuts in near-linear time
- On decomposing a hypergraph into \(k\) connected sub-hypergraphs
- On minimizing symmetric set functions
- On sparse subgraphs preserving connectivity properties
- On the shortest spanning subtree of a graph and the traveling salesman problem
- Random contractions and sampling for hypergraph and hedge connectivity
- Randomized approximation schemes for cuts and flows in capacitated graphs
- Realizing symmetric set functions as hypergraph cut capacity
- Sketching cuts in graphs and hypergraphs
- Strongly polynomial bounds for multiobjective and parametric global minimum cuts in graphs and hypergraphs
- The Minset-Poset Approach to Representations of Graph Connectivity
- Twice-Ramanujan sparsifiers
Cited in
(28)- Max Horn SAT and the minimum cut problem in directed hypergraphs
- Sparsest cuts and concurrent flows in product graphs.
- Computing minimum multiway cuts in hypergraphs
- Faster connectivity in low-rank hypergraphs via expander decomposition
- Incremental algorithm for minimum cut and edge connectivity in hypergraph
- Submodular reassignment problem for reallocating agents to tasks with synergy effects
- Multicriteria cuts and size-constrained \(k\)-cuts in hypergraphs
- All-Pairs Min-Cut in Sparse Networks
- Computing minimum cuts in hypergraphs
- Complete Minors in Graphs Without Sparse Cuts
- Hypergraph Cuts with General Splitting Functions
- Minimum cut and minimum k-cut in hypergraphs via branching contractions
- scientific article; zbMATH DE number 6783459 (Why is no real title available?)
- Minimal graph cuts on network subgraphs
- Hypergraph k-Cut for Fixed k in Deterministic Polynomial Time
- Minimum Cut and Minimum k -Cut in Hypergraphs via Branching Contractions
- Multicriteria Cuts and Size-Constrained k-Cuts in Hypergraphs.
- Deterministic enumeration of all minimum cut-sets and k-cut-sets in hypergraphs for fixed k
- A polynomial time algorithm for finding a minimum 4-partition of a submodular function
- Splitting-off in hypergraphs
- Bisection width, discrepancy, and eigenvalues of hypergraphs
- Splitting-off in hypergraphs
- Vertex sparsifiers for hyperedge connectivity
- Isolating cuts, (bi-)submodularity, and faster algorithms for connectivity
- Sublinear time hypergraph sparsification via cut and edge sampling queries
- Hypergraph connectivity augmentation in strongly polynomial time
- Mimicking networks for constrained multicuts in hypergraphs
- Algorithms for the determination of cutsets in a hypergraph
This page was built for publication: Minimum cuts and sparsification in hypergraphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4561257)
