Fully dynamic randomized algorithms for graph spanners

DOI10.1145/2344422.2344425zbMath1295.05221OpenAlexW2063860324MaRDI QIDQ3189078

Surender Baswana, Soumojit Sarkar, Sumeet Khurana

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/2344422.2344425

zbMATH Keywords

graph algorithmsgraph spannerdynamic algorithmapproximate shortest paths

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Randomized algorithms (68W20)

Related Items (16)

On resilient graph spanners ⋮ Incremental algorithm for maintaining a DFS tree for undirected graphs ⋮ Graph Sparsification, Spectral Sketches, and Faster Resistance Computation via Short Cycle Decompositions ⋮ Rumor Spreading with No Dependence on Conductance ⋮ Online Spanners in Metric Spaces ⋮ Fully Dynamic Maximal Matching in $O(\log n)$ Update Time (Corrected Version) ⋮ Distributed construction of purely additive spanners ⋮ Unnamed Item ⋮ Graph spanners: a tutorial review ⋮ Unnamed Item ⋮ Dynamic graph coloring ⋮ Randomization for Efficient Dynamic Graph Algorithms ⋮ Constant-time dynamic weight approximation for minimum spanning forest ⋮ Dynamic Approximate All-Pairs Shortest Paths: Breaking the $O(mn)$ Barrier and Derandomization ⋮ Dynamic DFS in Undirected Graphs: Breaking the $O(m)$ Barrier ⋮ Fully Dynamic Maximal Matching in $O(\log n)$ Update Time

This page was built for publication: Fully dynamic randomized algorithms for graph spanners