Oracles for distances avoiding a failed node or link

摘要

We consider the problem of preprocessing an edge-weighted directed graph G to answer queries that ask for the length and first hop of a shortest path from any given vertex x to any given vertex y avoiding any given vertex or edge. As a natural application, this problem models routing in networks subject to node or link failures. We describe a deterministic oracle with constant query time for this problem that uses O(n(2) log n) space, where n is the number of vertices in G. The construction time for our oracle is O(mn(2) + n(3) log n). However, if one is willing to settle for Theta(n(2.5)) space, we can improve the preprocessing time to O(mn(1.5) + n(2.5) log n) while maintaining the constant query time. Our algorithms can find the shortest path avoiding a failed node or link in time proportional to the length of the path.