# Faster Algorithms for Mining Shortest-Path Distances from Massive Time-Evolving Graphs
## 3 A New Algorithm: queue-2 hc
### Profiling of Algorithm bidir-2 hc
The backward cover graph \(B^{L}_{G}(x,y)\) is a subgraph of \(G\) with \(V^{\prime}\) and \(A^{\prime}\) as vertex and arc sets, respectively, as follows:_

* _a vertex_ \(u\) _is in_ \(V^{\prime}\) _if_ \(u\in V\) _and there exist two pairs_ \((h,\delta_{xh})\in L_{out}(x)\) _and_ \((h,\delta_{hy})\in L_{in}(v)\) _such that_ \(\delta_{xh}+\delta_{hy}=d_{G}(x,v)=w(x,y)+d_{G}(y,v)\) _(that is a shortest path from_ \(x\) _to_ \(u\) _includes_ \((x,y)\) _and_ \(h\) _is a hub vertex for pair_ \(x,v\)_);_
* _an arc_ \((u,v)\) _is in_ \(A^{\prime}\) _if_ \((u,v)\in A\) _and_ \(u,v\in V^{\prime}\) _(hence_ \(d_{G}(x,v)=w(x,y)+d_{G}(y,u)+w(u,v)\)_)._

In other words, analogously to the forward case, vertices of the backward cover graph are those having, in \(G\), a shortest path from \(x\) that might contain arc \((x,y)\) and hence whose distance from \(x\) might change as a consequence of a decremental operation occurring on \((x,y)\). Please note that again whether the distance from \(x\) changes or not depends on the number of shortest paths from the vertex from \(x\) that are in the graph, and on the vertex ordering. Note also that the arcs of such graph are the arcs of a shortest-path arborescence of \(G^{T}\) rooted at \(y\) plus arc \((x,y)\) (a toy example of the structure of cover graphs for a given input graph is shown in Figure 3b). Finally, we define the set of _forward invalid hubs_\(\mathtt{H}_{\mathtt{f}}(\mathtt{x},\mathtt{y})\subseteq\mathsf{V}\) (_backward invalid hubs_\(\mathtt{H}_{\mathtt{b}}(\mathtt{x},\mathtt{y})\subseteq\mathsf{V}\), respectively) of \((\mathtt{x},\mathtt{y})\) as follows. **Definition 3** (Forward Invalid Hubs). : _Given a graph \(\mathsf{G}=(\mathsf{V},\mathsf{A})\), a 2-hop-cover labeling \(\mathsf{L}\) of \(\mathsf{G}\) and an arc \((\mathtt{x},\mathtt{y})\in\mathsf{A}\). Then, the set of forward invalid hubs \(\mathtt{H}_{\mathtt{f}}(\mathtt{x},\mathtt{y})\) of \((\mathtt{x},\mathtt{y})\) is defined as:_

\[\mathtt{H}_{\mathtt{f}}(\mathtt{x},\mathtt{y})=\{\mathsf{h}\in\mathsf{V}:( \mathsf{h},\delta_{\mathtt{x}\mathsf{h}})\in\mathsf{L}_{\mathtt{out}}( \mathtt{x})\ \land\ (\mathsf{h},\delta_{\mathtt{y}\mathsf{h}})\in\mathsf{L}_{\mathtt{out}}( \mathtt{y})\ \land\ \mathtt{w}(\mathtt{x},\mathtt{y})+\delta_{\mathtt{y}\mathsf{h}}=\delta_{ \mathtt{x}\mathsf{h}}\}.\]

Similarly, we give a backward version. **Definition 4** (Backward Invalid Hubs). : _Given a graph \(\mathsf{G}=(\mathsf{V},\mathsf{A})\), a 2-hop-cover labeling \(\mathsf{L}\) of \(\mathsf{G}\) and an arc \((\mathtt{x},\mathtt{y})\in\mathsf{A}\). Then, the set of backward invalid hubs \(\mathtt{H}_{\mathtt{b}}(\mathtt{x},\mathtt{y})\) of \((\mathtt{x},\mathtt{y})\) is defined as:_

\[\mathtt{H}_{\mathtt{b}}(\mathtt{x},\mathtt{y})=\{\mathsf{h}\in\mathsf{V}:( \mathsf{h},\delta_{\mathtt{h}\mathtt{x}})\in\mathsf{L}_{\mathtt{in}}(\mathtt{ x})\ \land\ (\mathsf{h},\delta_{\mathtt{h}\mathtt{y}})\in\mathsf{L}_{\mathtt{in}}( \mathtt{y})\land\ \mathtt{w}(\mathtt{x},\mathtt{y})+\delta_{\mathtt{h} \mathtt{x}}=\delta_{\mathtt{h}\mathtt{y}}\}.\]

Given the above definitions, algorithm clean's strategy is based on the following properties. Notice that for the sake of simplicity, in what follows we use \(\mathtt{v}\in\mathsf{F}_{\mathsf{G}}^{\mathsf{L}}(\mathtt{x},\mathtt{y})\) or \(\mathtt{v}\in\mathsf{B}_{\mathsf{G}}^{\mathsf{L}}(\mathtt{x},\mathtt{y})\) to denote a vertex \(\mathtt{v}\) belonging to the vertex set of either the forward or the backward cover graph. **Property 2**. : _Let \(\mathsf{L}\) be a 2-hop-cover labeling of \(\mathsf{G}\). Assume arc \((\mathtt{x},\mathtt{y})\) is subject to a decremental operation and let \(\mathsf{G}^{\prime}\) be the graph obtained by applying to \(\mathsf{G}\) such modification. Let \(\mathsf{F}_{\mathsf{G}}^{\mathsf{L}}(\mathtt{x},\mathtt{y})\) (\(\mathsf{B}_{\mathsf{G}}^{\mathsf{L}}(\mathtt{x},\mathtt{y})\), resp.) be the forward (backward, resp.) cover graph.