Upper and lower bounds for fully retroactive graph problems
From MaRDI portal
Publication:832892
DOI10.1007/978-3-030-83508-8_34OpenAlexW3198709365MaRDI QIDQ832892
Xiaowei Wu, Monika R. Henzinger
Publication date: 25 March 2022
Full work available at URL: https://arxiv.org/abs/1910.03332
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Making data structures persistent
- A data structure for dynamic trees
- Maintaining Minimum Spanning Forests in Dynamic Graphs
- A Fully Dynamic Reachability Algorithm for Directed Graphs with an Almost Linear Update Time
- Unifying and Strengthening Hardness for Dynamic Problems via the Online Matrix-Vector Multiplication Conjecture
- Retroactive data structures
- Fully Retroactive Approximate Range and Nearest Neighbor Searching
- Randomized fully dynamic graph algorithms with polylogarithmic time per operation
- Polylogarithmic Fully Retroactive Priority Queues via Hierarchical Checkpointing
- Faster Fully-Dynamic Minimum Spanning Forest
- Cloning Voronoi Diagrams via Retroactive Data Structures
- Efficiency of a Good But Not Linear Set Union Algorithm
- Making data structures confluently persistent
- Fully Dynamic Maximal Matching in $O(\log n)$ Update Time (Corrected Version)
- A Deamortization Approach for Dynamic Spanner and Dynamic Maximal Matching
- Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity
- Logarithmic Lower Bounds in the Cell-Probe Model
