Approximate Shortest Paths Avoiding a Failed Vertex: Near Optimal Data Structures for Undirected Unweighted Graphs

摘要

Let G - (V, E) be an undirected unweighted graph. A path between any two vertices u,v e V is said to be t-approximate shortest path if its length is at most t times the length of the shortest path between ? and v. We address the problem of building a compact data structure which can efficiently answer the following query for any u, v, x ∈ V and t > 1:Report t-approximate shortest path between u and v when vertex x fails.We present data structures for the single source as well as all-pairs versions of this problem. The query time guaranteed by our data structures is optimal up to a constant factor. Moreover, the size of each of them nearly matches the size of the corresponding data structure with no failures.