Incremental approximate maximum flow via residual graph sparsification
From MaRDI portal
Cites work
- A general framework for graph sparsification
- A linear-time algorithm for finding a sparse \(k\)-connected spanning subgraph of a \(k\)-connected graph
- A Static 2-Approximation Algorithm for Vertex Connectivity and Incremental Approximation Algorithms for Edge and Vertex Connectivity
- Almost-linear time algorithms for decremental graphs: min-cost flow and more via duality
- Amortized efficiency of a path retrieval data structure
- An almost-linear-time algorithm for approximate max flow in undirected graphs, and its multicommodity generalizations
- Approximate undirected maximum flows in \(O(m\operatorname{polylog}(n))\) time
- Area-convexity, _ regularization, and undirected multicommodity flow
- Beyond the flow decomposition barrier
- Breaking the multicommodity flow barrier for o(√log n)-approximations to sparsest cut
- Dynamic Maxflow via Dynamic Interior Point Methods
- Efficient data structures for incremental exact and approximate maximum flow
- Fast augmenting paths by random sampling from residual graphs
- Fast dynamic cuts, distances and effective resistances via vertex sparsifiers
- Fully dynamic electrical flows: sparse maxflow faster than Goldberg-Rao
- Fully dynamic spectral vertex sparsifiers and applications
- Graph sparsification by effective resistances
- scientific article; zbMATH DE number 795214 (Why is no real title available?)
- scientific article; zbMATH DE number 7788470 (Why is no real title available?)
- Incremental approximate maximum flow on undirected graphs in subpolynomial update time
- Maximum flow and minimum-cost flow in almost-linear time
- Nearly maximum flows in nearly linear time
- On the hardness of partially dynamic graph problems and connections to diameter
- Randomized approximation schemes for cuts and flows in capacitated graphs
- Routing under balance
- Simple dynamic algorithms for maximal independent set, maximum flow and maximum matching
- Sparsification of directed graphs via cut balance
- The Laplacian paradigm: emerging algorithms for massive graphs
- The multiplicative weights update method: a meta-algorithm and applications
- Unifying and strengthening hardness for dynamic problems via the online matrix-vector multiplication conjecture
- Worst-case Analysis of Set Union Algorithms
This page was built for publication: Incremental approximate maximum flow via residual graph sparsification
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7349560)
