The power of vertex sparsifiers in dynamic graph algorithms

DOI10.4230/LIPICS.ESA.2017.45MaRDI QIDQ5111734zbMATHFDO

Authors Gramoz Goranci, Pan Peng, Monika R. Henzinger

Publication date 27 May 2020

Full work available at URL https://arxiv.org/abs/1712.06473

zbMATH Keywords

minor-free graphsdynamic graph algorithmsmax flowelectrical flow

Mathematics Subject Classification ID

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)

Recommendations

• Fully dynamic spectral vertex sparsifiers and applications
• Sparsification—a technique for speeding up dynamic graph algorithms
• scientific article; zbMATH DE number 1256641
• Improved guarantees for vertex sparsification in planar graphs
• Improved guarantees for vertex sparsification in planar graphs

Cites work

• scientific article; zbMATH DE number 3934150 (Why is no real title available?)
• A fully dynamic approximation scheme for shortest paths in planar graphs
• A linear work, \(O(n^{1/6})\) time, parallel algorithm for solving planar Laplacians
• A new approach to computing maximum flows using electrical flows
• An almost-linear-time algorithm for approximate max flow in undirected graphs, and its multicommodity generalizations
• Approaching optimality for solving SDD linear systems
• Approximate maximum flow on separable undirected graphs
• Approximate undirected maximum flows in \(O(m\operatorname{polylog}(n))\) time
• Approximation Algorithms for Multicommodity-Type Problems with Guarantees Independent of the Graph Size
• Electrical flows, Laplacian systems, and faster approximation of maximum flow in undirected graphs
• Fast Algorithms for Shortest Paths in Planar Graphs, with Applications
• Fully dynamic (2 + ε) approximate all-pairs shortest paths with fast query and close to linear update time
• Fully dynamic all-pairs shortest paths: breaking the \(O(n)\) barrier
• Fully dynamic approximate distance oracles for planar graphs via forbidden-set distance labels
• Fully dynamic planarity testing with applications
• Generalized Nested Dissection
• Graph sparsification by effective resistances
• Improved algorithms for min cut and max flow in undirected planar graphs
• Multiplying matrices faster than coppersmith-winograd
• Nearly linear time algorithms for preconditioning and solving symmetric, diagonally dominant linear systems
• Planar separators and parallel polygon triangulation.
• Routing in undirected graphs with constant congestion
• Sampling random spanning trees faster than matrix multiplication
• Separator based sparsification. I: Planarity testing and minimum spanning trees
• Single pass spectral sparsification in dynamic streams
• Spanning forests and the vector bundle Laplacian
• Spectral sparsification in the semi-streaming setting
• Spectral sparsification of graphs
• Structured recursive separator decompositions for planar graphs in linear time
• The multiplicative weights update method: a meta-algorithm and applications
• Towards \((1 + \varepsilon)\)-approximate flow sparsifiers
• Unifying and strengthening hardness for dynamic problems via the online matrix-vector multiplication conjecture

Cited in

(6)

• scientific article; zbMATH DE number 7378710 (Why is no real title available?)
• scientific article; zbMATH DE number 1256641 (Why is no real title available?)
• Fully dynamic spectral vertex sparsifiers and applications
• Vertex Sparsifiers: New Results from Old Techniques
• Decremental SSSP in Weighted Digraphs: Faster and Against an Adaptive Adversary
• 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)