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?V is said to be t-approximate shortest path if its length is at most t times the length of the shortest path between u 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.
shortest path distance approximate distance oracle