Fully dynamic algorithm for graph spanners with poly-logarithmic update time
Surender Baswana, Soumojit Sarkar · Symposium on Discrete Algorithms · 2008
Spanner of an undirected graph G = (V, E) is a sub graph which is sparse and yet preserves all-pairs distances approximately. More precisely, a spanner with stretch t ∈ IN is a subgraph (V, ES), ES ⊆ E such that the distance between any two vertices in the subgraph is at most t times their distance in G. We present two fully dynamic algorithms for maintaining a sparse t-spanner of an unweighted graph. Our first algorithm achieves expected O(7 t/4) time per update independent of the size of the graph. This algorithm is particularly of interest for maintaining small stretch spanners. Our second algorithm achieves expected O(polylog |V|) time per update irrespective of the stretch.