Streaming and fully dynamic centralized algorithms for constructing and maintaining sparse spanners

DOI10.1145/1921659.1921666zbMath1295.05232OpenAlexW2044246186MaRDI QIDQ3189002

Michael Elkin

Publication date: 9 September 2014

Published in: ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1921659.1921666

zbMATH Keywords

graph spannersstreaming algorithms

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (11)

On resilient graph spanners ⋮ Real-time monitoring of undirected networks: Articulation points, bridges, and connected and biconnected components ⋮ Decentralized Low-Stretch Trees via Low Diameter Graph Decompositions ⋮ Online Spanners in Metric Spaces ⋮ Single Pass Spectral Sparsification in Dynamic Streams ⋮ Unnamed Item ⋮ Graph spanners: a tutorial review ⋮ Dynamic Approximate All-Pairs Shortest Paths: Breaking the $O(mn)$ Barrier and Derandomization ⋮ Depth First Search in the Semi-streaming Model ⋮ Near-Optimal Approximate Shortest Paths and Transshipment in Distributed and Streaming Models ⋮ A Deterministic Almost-Tight Distributed Algorithm for Approximating Single-Source Shortest Paths

This page was built for publication: Streaming and fully dynamic centralized algorithms for constructing and maintaining sparse spanners