Faster connectivity in low-rank hypergraphs via expander decomposition
From MaRDI portal
Publication:2164680
DOI10.1007/978-3-031-06901-7_6zbMath1497.90210arXiv2011.08097OpenAlexW3100115795MaRDI QIDQ2164680
Danupon Nanongkai, Sagnik Mukhopadhyay, Karthekeyan Chandrasekaran, Calvin Beideman
Publication date: 16 August 2022
Full work available at URL: https://arxiv.org/abs/2011.08097
Related Items (1)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Minimizing symmetric submodular functions
- 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
- Computing Edge-Connectivity in Multigraphs and Capacitated Graphs
- A new approach to the minimum cut problem
- Minimum Cuts and Sparsification in Hypergraphs
- Computing minimum cuts in hypergraphs
- Random Contractions and Sampling for Hypergraph and Hedge Connectivity
- Local Flow Partitioning for Faster Edge Connectivity
- Deterministic Edge Connectivity in Near-Linear Time
- Dynamic spanning forest with worst-case update time: adaptive, Las Vegas, and O(n1/2 - ε)-time
- Fully-dynamic minimum spanning forest with improved worst-case update time
- Submatrix Maximum Queries in Monge and Partial Monge Matrices Are Equivalent to Predecessor Search
- Weighted min-cut: sequential, cut-query, and streaming algorithms
- Faster Algorithms for Edge Connectivity via Random 2-Out Contractions
- Computing and Testing Small Connectivity in Near-Linear Time and Queries via Fast Local Cut Algorithms
- Breaking quadratic time for small vertex connectivity and an approximation scheme
- Minimum Cut and Minimum k-Cut in Hypergraphs via Branching Contractions
- Expander Decomposition and Pruning: Faster, Stronger, and Simpler
- Minimum cuts in near-linear time
- Vertex connectivity in poly-logarithmic max-flows
This page was built for publication: Faster connectivity in low-rank hypergraphs via expander decomposition
