# 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
Then, for any vertex \(\mathtt{u}\in\mathsf{V}\) such that \(\mathtt{u}\
ot\in\mathsf{F}_{\mathsf{G}}^{\mathsf{L}}(\mathtt{x},\mathtt{y})\) (\(\mathtt{v}\
ot\in\mathsf{B}_{\mathsf{G}}^{\mathsf{L}}(\mathtt{x},\mathtt{y})\), resp.) we have that \(\mathsf{L}_{\mathtt{out}}(\mathtt{u})\) (\(\mathsf{L}_{\mathtt{in}}(\mathtt{u})\), resp.) contains only correct entries for \(\mathsf{G}^{\prime}\), that is for any \((\mathsf{h},\delta_{\mathtt{u}\mathsf{h}})\in\mathsf{L}_{\mathtt{out}}( \mathtt{u})\) we have \(\delta_{\mathtt{u}\mathsf{h}}=\mathsf{d}_{\mathsf{G}}(\mathtt{u},\mathtt{h})= \mathsf{d}_{\mathsf{G}}^{\prime}(\mathtt{u},\mathtt{h})\) (for any \((\mathsf{h},\delta_{\mathtt{h}\mathsf{u}})\in\mathsf{L}_{\mathtt{in}}( \mathtt{u})\) we have \(\delta_{\mathtt{h}\mathsf{u}}=\mathsf{d}_{\mathsf{G}}(\mathtt{h},\mathtt{u})= \mathsf{d}_{\mathsf{G}}^{\prime}(\mathtt{h},\mathtt{u})\), resp. )._

Proof. : By definition of forward cover graph, we know \(\mathtt{u}\
ot\in\mathsf{F}_{\mathsf{G}}^{\mathsf{L}}(\mathtt{x},\mathtt{y})\) implies there does not exist two pairs \((\mathsf{h},\delta_{\mathtt{u}\mathsf{h}})\in\mathsf{L}_{\mathtt{out}}( \mathtt{u})\) and \((\mathsf{h},\delta_{\mathtt{h}\mathtt{y}})\in\mathsf{L}_{\mathtt{in}}( \mathtt{y})\) such that \(\delta_{\mathtt{u}\mathsf{h}}+\delta_{\mathtt{h}\mathtt{y}}=\mathsf{d}_{ \mathsf{G}}(\mathtt{u},\mathtt{y})=\mathsf{d}_{\mathsf{G}}(\mathtt{u},\mathtt{ x})+w(\mathtt{x},\mathtt{y})\) for some \(\mathtt{h}\in\mathsf{V}\). Observe that for any 2-hop-cover labeling, \((\mathsf{h},\delta_{\mathtt{u}\mathsf{h}})\in\mathsf{L}_{\mathtt{out}}( \mathtt{u})\), for some \(\mathtt{h}\in\mathsf{V}\), implies \((\mathsf{h},\delta_{\mathtt{h}\mathsf{h}}=\emptyset)\in\mathsf{L}_{\mathtt{in}}( \mathtt{h})\). Now, by contradiction, assume an entry \((\mathsf{h},\delta_{\mathtt{u}\mathsf{h}})\in\mathsf{L}_{\mathtt{out}}( \mathtt{u})\) is outdated, that is \(\delta_{\mathtt{u}\mathsf{h}}=\mathsf{d}_{\mathsf{G}}(\mathtt{u},\mathtt{h}) \
eq\mathsf{d}_{\mathsf{G}}^{\mathsf{L}}(\mathtt{u},\mathtt{h})\). This implies that the only shortest path from \(\mathtt{u}\) to \(\mathtt{y}\) in \(\mathsf{G}\) includes arc \((\mathtt{x},\mathtt{y})\) (since the update is decremental we have that \(w(\mathtt{x},\mathtt{y})\) increases) and \(\mathtt{h}\) is a hub vertex for pair \(\mathtt{u}\), \(\mathtt{h}\). Hence we would have \(\mathtt{u}\) is in the forward cover graph since there exist pairs \((\mathsf{h},\delta_{\mathtt{u}\mathsf{h}})\in\mathsf{L}_{\mathtt{out}}( \mathtt{u})\) and \((\mathsf{h},\delta_{\mathtt{h}\mathsf{h}}=\emptyset)\in\mathsf{L}_{\mathtt{in}}( \mathtt{h})\) such that \(\delta_{\mathtt{u}\mathsf{h}}+\delta_{\mathtt{h}\mathsf{h}}=\mathsf{d}_{ \mathsf{G}}(\mathtt{u},\mathtt{h})=\mathsf{d}_{\mathsf{G}}(\mathtt{u},\mathtt{x} )+w(\mathtt{x},\mathtt{y})\), which is a contradiction. The proof for the backward version is symmetric. **Corollary 1**. : _For any pair \(\mathtt{u},\mathtt{v}\in\mathsf{V}\) such that \(\mathtt{u}\
ot\in\mathsf{F}_{\mathsf{G}}^{\mathsf{L}}(\mathtt{x},\mathtt{y})\) and \(\mathtt{v}\
ot\in\mathsf{B}_{\mathsf{G}}^{\mathsf{L}}(\mathtt{x},\mathtt{y})\), we have that labeling \(\mathsf{L}\) covers the pair also for \(\mathsf{G}^{\prime}\), that is \(\mathsf{Q}(\mathtt{u},\mathtt{v},\mathsf{L})=\mathsf{d}_{\mathsf{G}}( \mathtt{u},\mathtt{v})=\mathsf{d}_{\mathsf{G}^{\prime}}(\mathtt{u},\mathtt{ v})\)._

Figure 3: (a): assume all arcs in this example have unitary weight and the vertex ordering is \(\{\mathtt{x}_{0},\mathtt{x}_{1},\ldots,\mathtt{x}_{4}\}\). Both \(\mathtt{x}_{4}\) and \(\mathtt{x}_{3}\) are in \(\mathsf{F}_{\mathsf{G}}^{\mathsf{L}}(\mathtt{x}_{1},\mathtt{x}_{0})\) since the hub vertex for pairs \(\mathtt{x}_{4},\mathtt{x}_{0}\) and \(\mathtt{x}_{3},\mathtt{x}_{0}\), in the labeling \(\mathsf{L}\) induced by the above ordering, is vertex \(\mathtt{x}_{0}\).