The power of vertex sparsifiers in dynamic graph algorithms
DOI10.4230/LIPICS.ESA.2017.45zbMATH Open1442.68172arXiv1712.06473MaRDI QIDQ5111734FDOQ5111734
Authors: Gramoz Goranci, Pan Peng, Monika R. Henzinger 
Publication date: 27 May 2020
Full work available at URL: https://arxiv.org/abs/1712.06473
Recommendations
Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20) Analysis of algorithms (68W40) Approximation algorithms (68W25) Flows in graphs (05C21) Applications of graph theory to circuits and networks (94C15)
Cites Work
- Generalized Nested Dissection
- A linear work, \(O(n^{1/6})\) time, parallel algorithm for solving planar Laplacians
- Nearly linear time algorithms for preconditioning and solving symmetric, diagonally dominant linear systems
- Spectral sparsification of graphs
- Title not available (Why is that?)
- Multiplying matrices faster than coppersmith-winograd
- Approaching optimality for solving SDD linear systems
- Graph sparsification by effective resistances
- The multiplicative weights update method: a meta-algorithm and applications
- Electrical flows, Laplacian systems, and faster approximation of maximum flow in undirected graphs
- Fast Algorithms for Shortest Paths in Planar Graphs, with Applications
- Spanning forests and the vector bundle Laplacian
- Single pass spectral sparsification in dynamic streams
- Spectral sparsification in the semi-streaming setting
- Improved algorithms for min cut and max flow in undirected planar graphs
- Fully dynamic (2 + ε) approximate all-pairs shortest paths with fast query and close to linear update time
- Planar separators and parallel polygon triangulation.
- Unifying and strengthening hardness for dynamic problems via the online matrix-vector multiplication conjecture
- Fully dynamic planarity testing with applications
- Structured recursive separator decompositions for planar graphs in linear time
- Approximate maximum flow on separable undirected graphs
- Separator based sparsification. I: Planarity testing and minimum spanning trees
- Approximation Algorithms for Multicommodity-Type Problems with Guarantees Independent of the Graph Size
- A fully dynamic approximation scheme for shortest paths in planar graphs
- An almost-linear-time algorithm for approximate max flow in undirected graphs, and its multicommodity generalizations
- Routing in undirected graphs with constant congestion
- Sampling random spanning trees faster than matrix multiplication
- Fully dynamic approximate distance oracles for planar graphs via forbidden-set distance labels
- A new approach to computing maximum flows using electrical flows
- Towards \((1 + \varepsilon)\)-approximate flow sparsifiers
- Fully dynamic all-pairs shortest paths: breaking the \(O(n)\) barrier
- Approximate undirected maximum flows in \(O(m\operatorname{polylog}(n))\) time
Cited In (6)
- Decremental SSSP in Weighted Digraphs: Faster and Against an Adaptive Adversary
- Title not available (Why is that?)
- Vertex Sparsifiers: New Results from Old Techniques
- Title not available (Why is that?)
- Fully dynamic spectral vertex sparsifiers and applications
- Fully dynamic randomized algorithms for graph spanners
This page was built for publication: The power of vertex sparsifiers in dynamic graph algorithms
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5111734)
