# Polynomial Time Algorithm for Shortest Paths in Interval Temporal Graphs +
## 4 Experimental Results
### Run Times  
Since the \(CSG\)s are much larger in size as compared to the corresponding \(ITG\)s, the reading time (from disk) of the \(CSG\) is also significantly larger. The comparison of the reading times for the graphs by our algorithm and by that of [PERSON] et al. (2015) is reported in Table 4. It is important to note that the reading times for our algorithm are almost the same for the different values of \(\mu_{D}\). However, for the \(CSG\)s, the reading time increases proportionately to the increase in the activity factor. This is because the number of contact sequence edges also increases proportionately. The size of the \(ITG\) representation, however, remains almost similar across different values of the parameter \(\mu_{D}\). Comparisons of run times (excluding the time to read in the temporal graph) of the two algorithms on all the datasets are reported in Table 5. As expected, the run times of our algorithm remains almost the same across the different values of \(\mu_{D}\). However, the run times of times of the algorithm in ([PERSON] et al., 2015) increases proportionately to the increase in the value of \(\mu_{D}\) and, hence, the number of contact sequence edges in the graph. Therefore, our algorithm shows increasing performance gains in run time and in memory consumption over that of [PERSON] et al. (2015) when the temporal graph has larger contiguous travel intervals. For our experiments, we limited the duration of the travel intervals to follow a normal distribution around \(\mu_{D}=50\). This is because for much larger travel intervals, the algorithm of [PERSON] et al. (2015) runs out of memory due to the large number of contact sequence edges. In contrast, our algorithm comfortably handles large travel durations. One example of this is the _growth_ dataset for which our algorithm runs in reasonable times for the values of \(\mu_{D}=20\) and \(\mu_{D}=50\), whereas it is infeasible to represent the \(CSG\) using 32-_bit_ integers for \(\mu_{D}=20\). The performance gains obtained by our algorithm over that of [PERSON] et al. (2015) with increasing activity factor are shown in Figure 8. \begin{table}
\begin{tabular}{c c c c c c} \hline \hline  & \multicolumn{4}{c}{**Graphs with \(\mu_{I}=4,\mu_{I}=3\)**} \\ \hline \hline
**Dataset** & \(|V|\) & \(|E_{s}|\) & **cs-Edges** & **cs-Edges** & **cs-Edges** \\  & & & (\(\mu_{D}=5\)) & (\(\mu_{D}=20\)) & (\(\mu_{D}=50\)) \\ \hline \hline epin & 131.8 K & 840.8 K & 17.8 M & 65.2 M & 160.6 M \\ elec & 7119 & 103.6 K & 2.2 M & 8 M & 19.8 M \\ fb & 63.7 K & 817 K & 173.3 M & 633 M & 156 M \\ growth & 1870.7 K & 39,953 K & 848.3 M & – & – \\ youtube & 3.2 M & 9.3 M & 199 M & 727.2 M & 1.8B \\ digg & 30.3 K & 85.2 K & 1.8 M & 6.6 M & 16.2 M \\ slash & 51 K & 130.3 K & 2.7 M & 10.1 M & 24.9 M \\ conflict & 118 K & 2027.8 K & 43.07 M & 157.3 M & 387.5 M \\ arxiv & 28 K & 3148 K & 66.8 M & 244.2 M & 601.7 M \\ enron & 87,274 & 320.1 K & 6.8 M & 24.8 M & 61.1 M \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Synthetic graphs’ statistics. \begin{table}
\begin{tabular}{c c c c c c c} \hline \hline \multirow{2}{*}{**Dataset**} & \multicolumn{4}{c}{**ITG**} & \multicolumn{4}{c}{**CSG**} \\ \cline{2-7}  & \(\mu_{D}=5\) & \(\mu_{D}=20\) & \(\mu_{D}=50\) & \(\mu_{D}=5\) & \(\mu_{D}=20\) & \(\mu_{D}=50\) \\ \hline epin & 51.93 MB & 51.94 MB & 51.95 MB & 323 MB & 1.18 GB & 2.9 GB \\ elec & 6.2 MB & 6.23 MB & 6.23 MB & 36.1 MB & 132.2 MB & 325.7 MB \\ fb & 50.5 MB & 50.5 MB & 50.5 MB & 314.8 MB & 1.1 GB & 2.83 GB \\ growth & 2.55 GB & 2.55 GB & 2.55 GB & 17.1 GB & – & – \\ youtube & 609.3 MB & 609.3 MB & 609.3 MB & 4.2 GB & 15.5 GB & 38.1 GB \\ digg & 5.2 MB & 5.2 MB & 5.2 MB & 31.4 MB & 114.8 MB & 282.6 MB \\ slash & 8 MB & 8 MB & 8 MB & 49 M & 179.4 MB & 442.2 MB \\ conflict & 126 MB & 126 MB & 126 MB & 794.5 MB & 2.9 GB & 7.1 GB \\ arxiv & 191.8 MB & 191.8 MB & 191.8 MB & 1.15 GB & 4.21 GB & 10.37 GB \\ enron & 19.58 MB & 19.58 MB & 19.58 MB & 1.18 GB & 4.3 GB & 10.7 GB \\ \hline \hline \end{tabular}
\end{table} 
Table 3: Synthetic graphs’ size on disk.