| We study the decremental All-Pairs Shortest Paths (APSP) problem in undirected edge-weighted graphs. The input to the problem is an undirected n-vertex m-edge graph G with non-negative lengths on edges, that undergoes an online sequence of edge deletions. The goal is to support approximate shortest-paths queries: given a pair x, y of vertices of G, return a path P connecting x to y, whose length is within factor α of the length of the shortest x-y path, in time *O( |
E(P) |
)*, where α is the approximation factor of the algorithm. |
Tags