The power of vertex sparsifiers in dynamic graph algorithms

DOI10.4230/LIPICS.ESA.2017.45zbMATH Open1442.68172arXiv1712.06473MaRDI QIDQ5111734FDOQ5111734

Gramoz Goranci, Pan Peng, Monika R. Henzinger

Publication date: 27 May 2020

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

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

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)

Cites Work

• Generalized Nested Dissection
• Title not available (Why is that?)
• 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 + ∊)-Approximate Flow Sparsifiers
• Preserving Terminal Distances Using Minors
• Fully Dynamic All-Pairs Shortest Paths: Breaking the O(n) Barrier
• Approximate Undirected Maximum Flows in O(mpolylog(n)) Time

Cited In (5)

• 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 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)