Let $G=(V,E)$ be any undirected graph on $V$ vertices and$E$ edges. A path $textbf{P}$ between any two vertices $u,vin 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 consider the problem of building a compact data structure for agiven graph $G$ which is capable of answering the following query forany $u,v,zin V$ and $t>1$.centerline{em report $t$-approximate shortest path between $u$ and $v$ when vertex $z$ fails}We present data structures for the single source as well all-pairs versions of this problem. Our data structures guarantee optimal query time. Most impressive feature of our data structures is that their size {em nearly} match the size of their best static counterparts.
展开▼
机译：令$ G =（V，E）$是$ V $顶点和$ E $边上的任何无向图。如果两个顶点$ u，vin V $之间的路径$ textbf {P} $的长度最大为$ t $乘以$ u $与之间的最短路径的长度，则该路径称为$ t $-近似最短路径。 $ v $。我们考虑为给定图$ G $建立紧凑的数据结构的问题，该结构可以回答以下查询任何$ u，v，zin V $和$ t> 1 $ .centerline {em report $ t顶点$ z $失败时，$ u $和$ v $之间的$近似最短路径}我们介绍了此问题的单个来源以及所有对版本的数据结构。我们的数据结构可确保最佳查询时间。我们数据结构最令人印象深刻的特征是它们的大小与最佳静态副本的大小相近。
展开▼
