A New Deterministic Algorithm for Fully Dynamic All-Pairs Shortest Paths

We study the fully dynamic All-Pairs Shortest Paths (APSP) problem in undirected edge-weighted graphs. Given an n -vertex graph G with non-negative edge lengths, that undergoes an online sequence of edge insertions and deletions, the goal is to support approximate distance queries and shortest-path queries. We provide a deterministic algorithm for this problem, that, for a given precision parameter є, achieves approximation factor (loglog n ) 2 O (1/є 3 ) , and has amortized update time O ( n є log L ) per operation, where L is the ratio of longest to shortest edge length. Query time for distance-query is O (2 O (1/є) · log n · loglog L ), and query time for shortest-path query is O (| E ( P )|+2 O (1/є) · log n · loglog L ), where P is the path that the algorithm returns. To the best of our knowledge, even allowing any o ( n )-approximation factor, no adaptive-update algorithms with better than Θ( m ) amortized update time and better than Θ( n ) query time were known prior to this work. We also note that our guarantees are stronger than the best current guarantees for APSP in decremental graphs in the adaptive-adversary setting.

Authors

• Julia Chuzhoy
• Ruimin Zhang

Keywords

• all-pairs shortest path
• fully dynamic algorithm