Fully dynamic randomized algorithms for graph spanners
From MaRDI portal
Recommendations
- Dynamic Algorithms for Graph Spanners
- Randomization for efficient dynamic graph algorithms (invited talk)
- Randomized fully dynamic graph algorithms with polylogarithmic time per operation
- scientific article; zbMATH DE number 1263228
- Dynamic algorithms for geometric spanners of small diameter: Randomized solutions
- A simple and linear time randomized algorithm for computing sparse spanners in weighted graphs
- Fully dynamic algorithms for chordal graphs and split graphs
- The power of vertex sparsifiers in dynamic graph algorithms
- scientific article; zbMATH DE number 1305520
Cited in
(33)- Dynamic algorithms for geometric spanners of small diameter: Randomized solutions
- Graph spanners: a tutorial review
- Constant-time dynamic weight approximation for minimum spanning forest
- Incremental algorithm for maintaining a DFS tree for undirected graphs
- Randomization for efficient dynamic graph algorithms (invited talk)
- Dynamic approximate all-pairs shortest paths: breaking the \(O(mn)\) barrier and derandomization
- Rumor spreading with no dependence on conductance
- Randomized k-server algorithms for growth-rate bounded graphs
- Streaming and fully dynamic centralized algorithms for constructing and maintaining sparse spanners
- Very fast construction of bounded‐degree spanning graphs via the semi‐random graph process
- scientific article; zbMATH DE number 1305520 (Why is no real title available?)
- Fully dynamic spanners with worst-case update time
- Fully dynamic maximal matching in O( n) update time (corrected version)
- Local computation algorithms for spanners
- Fault tolerant and fully dynamic DFS in undirected graphs: simple yet efficient
- Dynamic DFS in undirected graphs: breaking the \(O(m)\) barrier
- Fully dynamic maximal matching in O( n) update time
- Small Stretch Spanners on Dynamic Graphs
- A near-optimal distributed fully dynamic algorithm for maintaining sparse spanners
- Streaming and Fully Dynamic Centralized Algorithms for Constructing and Maintaining Sparse Spanners
- Dynamic Algorithms for Graph Spanners
- Algorithms – ESA 2005
- scientific article; zbMATH DE number 6469207 (Why is no real title available?)
- Dynamic graph coloring
- Graph Sparsification, Spectral Sketches, and Faster Resistance Computation via Short Cycle Decompositions
- Online Spanners in Metric Spaces
- A new deterministic algorithm for fully dynamic all-pairs shortest paths
- Deterministic incremental APSP with polylogarithmic update time and stretch
- New tradeoffs for decremental approximate all-pairs shortest paths
- Online spanners in metric spaces
- Simple dynamic spanners with near-optimal recourse against an adaptive adversary
- Online Euclidean spanners
- Constant-round spanners and shortest paths in congested clique and MPC
This page was built for publication: Fully dynamic randomized algorithms for graph spanners
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3189078)
