On the streaming complexity of expander decomposition
From MaRDI portal
Cites work
- A deterministic algorithm for balanced cut with applications to dynamic connectivity, flows, and beyond
- A general framework for graph sparsification
- Approximation algorithms for unique games
- Deterministic mincut in almost-linear time
- Efficient algorithms for semirandom planted CSPs at the refutation threshold
- Expander decomposition and pruning: faster, stronger, and simpler
- Expander decomposition in dynamic streams
- Fast and Space Efficient Spectral Sparsification in Dynamic Streams
- Fully dynamic exact edge connectivity in sublinear time
- Graph Clustering using Effective Resistance
- Graph Sparsification in the Semi-streaming Model
- Graph sparsification, spectral sketches, and faster resistance computation, via short cycle decompositions
- scientific article; zbMATH DE number 437525 (Why is no real title available?)
- scientific article; zbMATH DE number 7053292 (Why is no real title available?)
- scientific article; zbMATH DE number 7788470 (Why is no real title available?)
- Improved distributed expander decomposition and nearly optimal triangle enumeration
- Maintaining expander decompositions via sparse cuts
- Maximum flow and minimum-cost flow in almost-linear time
- Near-linear time approximations for cut problems via fair cuts
- Near-optimal Distributed Triangle Enumeration via Expander Decompositions
- Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems
- On the hardness of approximating Multicut and Sparsest-Cut
- On weighted graph sparsification by linear sketching
- Random sampling in cut, flow, and network design problems
- Randomized approximation schemes for cuts and flows in capacitated graphs
- Single pass spectral sparsification in dynamic streams
- Singular value approximation and sparsifying random walks on directed graphs
- Spectral sparsification of graphs
- Towards tight bounds for spectral sparsification of hypergraphs
This page was built for publication: On the streaming complexity of expander decomposition
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6875157)
