# Faster Algorithms for Mining Shortest-Path Distances from Massive Time-Evolving Graphs
## 3 A New Algorithm: queue-2 hc
### Complexity of queue-2 hc  
In this section, we provide the complexity analysis of queue-2 hc. We start by bounding the worst-case running time of Algorithm clean. All results refer to a graph with \(n\) vertices and \(m\) arcs. Theorem 3.2: _Algorithm 3 runs in \(O(mn+n^{2}\log n)\) worst-case time per graph update._  
Proof. : First of all, it is easy to observe line 1 takes linear time in the size of the two involved label sets (that of \(x\) and that of \(y\)). In fact, computing \(H_{\ell}(x,y)\) and \(H_{b}(x,y)\) requires several comparisons, each taking \(O(1)\) time, that is equal to the size of the two label sets (that can be scanned in order regarding vertex ordering, as in Algorithm 1). Therefore, if we call \(|L|\) the size of the largest label (containing the largest number of pairs), then this step takes \(O(|L|)\) worst cast time, which is \(O(n)\). Now, we bound the computational time of procedure fclean, which is equal to that procedure bclean (which operates symmetrically on the graph and on the labeling). Specifically, it is easy to see that the initialization phase of mark and o_removal costs \(O(n)\), while the cycle of lines 7-20 is simply a shortest-path driven visit of the forward cover graph, which mimics [PERSON]'s algorithm (hence this would require \(O(m+n\log n)\)). The only difference consists of the tests of lines 9-17, whose purpose is to determine where entries are actually outdated, and in the condition for continuing the visit (membership to the cover graph) that is checked in line 18. Each execution of the former requires \(O(|H_{b}(x,y)|\cdot|N_{out}(v)|=O(n)\) worst-case time every time a vertex \(v\) is dequeued while the latter costs \(O(|L|)\) per arc relax operation. Thus, the cost of this visit is upperbounded by \(O(mn+n^{2}\log n)\). Finally, removal of outdated entries (lines 6-9) requires, in the worst case, to execute two label set scans (once for the outgoing label and once for the incoming label) per vertex of the graph. Each scan costs \(O(|L|)=O(n)\) thus the running time of this part is upperbounded by \(O(n|L|)=O(n^{2})\). Theorem 4.1: _Algorithm 4 requires \(O(n^{3}\log n)\) worst-case time per graph update._  
Proof: We bound the cost of lines 4-16, i.e., for handling the case of \(h\in\mathtt{IN}\). In fact, note that the running time of the procedure for handling the case of \(h\in\mathtt{OUT}\) is asymptotically the same. Now, observe that for each \(h\in\mathtt{IN}\), we first scan the vertices in \(\mathtt{OUT}\) to search for viable neighbors. This costs \(|N_{out}(v)||L|=O(n^{2})\) for a vertex \(v\), if again we call \(|L|\) the size of the largest label. Moreover, again for each \(h\in\mathtt{IN}\), we perform a shortest-path driven visit of the graph, whose worst-case running time is \(O(m+n^{2}\log n)\), since we need to add an extra \(O(|L|)=O(n)\) factor whenever we dequeue a vertex, for testing the cover property and possibly adding a label. Thus, for each vertex \(h\in\mathtt{IN}\) the worst-case running time is \(O(m+n^{2}\log n)\). Hence, since the number of vertices in \(\mathtt{IN}\) is \(O(n)\), we obtain a total running time for the procedure of \(O(mn+n^{3}\log n)=O(n^{3}\log n)\). Therefore, we can summarize the complexity of Algorithm queue-2 hc as follows. Theorem 4.2: _Algorithm queue-2 hc requires \(O(n^{3}\log n)\) worst-case time per graph update._  
Proof: The claim follows by the proofs of Theorems 2-3. By the above, it is easy to notice that given a graph update, queue-2 hc in the worst-case is slower than recomputing the labeling from scratch (which takes \(O(mn+n^{2}\log n)\) worst-case time). However, we show in the next section that experimentally queue-2 hc is much faster in all tested instances. Regarding bidir-2 hc, it is not trivial to understand, on a theoretical basis, whether asymptotically speaking its performance is better or worse than that of queue-2 hc, since the two time complexities depend on different parameters.