# On Finding Optimal (Dynamic) Arborescences
## 6 Conclusions  
We provided implementations of [PERSON] algorithm and of the Tarjan algorithm for determining optimal arborescences on directed and weighted graphs. Our implementation of the Tarjan Algorithm incorporated the corrections by [PERSON] et al., and it ran in \((m\log n)\) time, where \(n\) is the number of vertices of the graph, and \(m\) is the number of edges. We also provided an implementation for the dynamic updating of optimal arborescences based on the ideas by [PERSON], [PERSON], and [PERSON] that relies on the Tarjan algorithm running in \(O(n+||\rho||\log|\rho|)\) per update operation, where \(|\rho|\) and \(||\rho||\) are, respectively, the number of affected vertices and edges that scale linearly with respect to the memory usage. We highlight the fact that our implementations are generic in the sense that a generic comparator was given as a parameter, and, hence, we were not restricted to weighted graphs; we can find the optimal arborescence on any graph equipped with a total order on the set of edges. To our knowledge, our implementation for the optimal arborescence problem for dynamic graphs is the first one to be publicly available. The code is available at [[https://gitlab.com/espadas/optimal-arborescences](https://gitlab.com/espadas/optimal-arborescences)]([https://gitlab.com/espadas/optimal-arborescences](https://gitlab.com/espadas/optimal-arborescences)) (accessed on 4 November 2023). Experimental evaluation shows that our implementations comply with the expected theoretical bounds. Moreover, while multiple changes occurred in \(G\), the dynamic updating was at least twice as fast as the ab initio computation, thereby requiring more memory, even if by a constant factor. Our experimental results also corroborate the results presented by [PERSON] et al. and [PERSON] et al. We found one shortcoming regarding the dynamic optimal arborescence, namely, the high dependence between the time needed to recalculate the optimum arborescence and the affected level of the ATree. The lower the level, the larger the number of affected constituents will be. A prospect to achieve a more efficient dynamic algorithm could be relying on link-cut trees ([PERSON] and [PERSON], 2017), which maintains a collection of node-disjoint forests of self-adjusting binary \begin{table}
\begin{tabular}{c c c c} \hline \hline
**Dataset** & **Ab Initio \%** & **Dynamic Updating (MB)** & **Memory Ratio** \\ \hline
10 & 62.60 & 210.45 & 3.36 \\
20 & 154.52 & 520.83 & 3.37 \\
30 & 319.87 & 1041.22 & 3.26 \\
40 & 575.05 & 1772.00 & 5.54 \\
50 & 886.04 & 2667.96 & 3.01 \\
60 & 1274.59 & 3883.46 & 3.04 \\
70 & 1754.89 & 5242.21 & 2.99 \\
80 & 2285.91 & 6841.03 & 2.99 \\
90 & 2872.80 & 8574.12 & 2.99 \\
100 & 3435.51 & 10,482.84 & 3.05 \\ \hline \hline \end{tabular}
\end{table} 
Table 6: Memory usage comparison for the dynamic updating and ab initio computation of an optimal arborescence for the _Salmonella_Achtman7 GeneMLST_ dataset. \begin{table}
\begin{tabular}{c c c c} \hline \hline
**Dataset** & **Ab Initio** & **Dynamic Updating** & **Memory Ratio** \\
**\%** & **(MB)** & **(MB)** & **Memory Ratio** \\ \hline
10 & 125.32 & 415.93 & 3.32 \\
20 & 156.31 & 513.5 & 3.29 \\
30 & 214.65 & 680.62 & 3.17 \\
40 & 295.80 & 908.01 & 3.07 \\
50 & 411.26 & 1201.33 & 2.92 \\
60 & 534.45 & 1585.99 & 2.97 \\
70 & 714.39 & 2056.44 & 2.88 \\
80 & 898.64 & 2479.41 & 2.76 \\
90 & 1098.49 & 3026.20 & 2.75 \\
100 & 1306.95 & 3640.20 & 2.79 \\ \hline \hline \end{tabular}
\end{table} 
Table 5: Memory usage comparison for the dynamic updating and ab initio computation of an optimal arborescence for the _Yersinia_avgMLST_ dataset. heaps (splay trees [36]) under a sequence of LINK and CUT operations. Both operation take \(O(\log n)\) time in the worst case. With respect to the application in the phylogenetic inference context, we highlight the fact that the proposed implementation for dynamic updates makes it possible to significantly improve the time required to update phylogenetic patterns as datasets grow in size.