Anastasiia Alokhina

Fully Dynamic Shortest Path Reporting Against an Adaptive Adversary

2023 · arXiv (Cornell University)

Algebraic data structures are the main subroutine for maintaining distances in fully dynamic graphs in subquadratic time. However, these dynamic algebraic algorithms generally cannot maintain the shortest paths, especially against adaptive adversaries. We present the …