Expand description
Graph data structure for fast short-distance queries. Data structure used to answer short-distance queries. The data structure has one central parameter called the “depth” of the augmentation.
Concretely, given a graph $G$ and a depth $d \geq 1$, the augumentation computes an augmentation $\vec G_d$ in time $O(\|G\|)$ (treating $d$ as a constant). This augmentation can answer small distance queries of vertex-pairs in $G$ in constant time, that is, given $u, v \in G$ the augmentation $\vec G_d$ tells us in constant time the distance between $u$ and $v$ in $G$ if that distance is $\leq d$. Otherwise it will correctly tell us that the distance is $> d$.
The data structure $\vec G_d$ is itself a weighted digraph. The query described above is based on two properties:
- The in-degree of $\vec G_d$ is small if $G$ has certain good properties, and
- for $u,v \in G$ with distance $d’ \leq d$ we either have that $u$ and $v$ are joined by an arc of weight $d’$ in $\vec G_d$, or there exists a joint in-neighbour $w$ such that the weights of the arcs $wv$ and $wv$ sum up to $d’$.