# On Finding Optimal (Dynamic) Arborescences
## 5 Experimental Evaluation
### Dynamic Optimal Arborescences  
Let us compare the performance of maintaining dynamic optimal arborescences versus ab initio computation on edge updates. Both implementations rely on the algorithm derived by [PERSON] that is described in this paper. Our experiments consisted pf evaluating the running time and required memory for adding and deleting edges. The results were averaged over a sequence of 10 independent DELETE operations and also over a sequence  
Figure 16: Comparison of three different heap implementations within the [PERSON] algorithm sparse scale-free graphs. (**a**) Running time for scale-free graphs. (**b**) Running time for duplication model graphs. (**c**) Memory for scale-free graphs. (**d**) Memory for duplication model graphs. of 10 independent ADD operations. The sequences of edges subject to deletion or insertion were randomly selected. Figure 17a provides the results for the DELETE operations. We observe that updating the arborescence was twice as fast compared to its ab initio computation. Note that these results are aligned with the results presented by [PERSON], [PERSON], and [PERSON] [21]. Figures 18a-22a provide the results for the DELETE operation with respect to the phylogenetic data described above. As the size of the dataset grew, and the inferred graph became larger, and the dynamic updating also became more competitive, being twice as fast when compared with the ab initio computation. The results for the ADD operations are presented in Figure 17b for complete graphs and in Figures 18b-22b. It is clearly perceived that the ab initio computation was outmatched by the dynamic updating, in particular as the size of the graph grew. The dynamic updating was consistently at least twice as fast as the ab initio computation, thereby often surpassing that speedup factor. Figure 17: Optimal arborescence updating versus ab initio computation for DELETE and ADD operations for complete graphs. Running time averaged over 10 random operations. (**a**) DELETE operations. (**b**) ADD operations. Figure 18: Optimal arborescence updating versus ab initio computation for DELETE and ADD operations for _clostridium.Griffiths_ dataset. Running time averaged over 10 random operations. (**a**) DELETE operations. (**b**) ADD operations. Figure 19: Optimal arborescence updating versus ab initio computation for DELETE and ADD operations for _Moraxella.Achtman7 GeneMLST_ dataset. Running time averaged over 10 random operations. (a) DELETE operations. (b) ADD operations. Figure 20: Optimal arborescence updating versus ab initio computation for DELETE and ADD operations for _Salmonella.Achtman7 GeneMLST_ dataset. Running time averaged over 10 random operations. (a) DELETE operations. (b) ADD operations. Figure 19: Optimal arborescence updating versus ab initio computation for DELETE and ADD operations for _Moraxella.Achtman7 GeneMLST_ dataset. Running time averaged over 10 random operations. (a) DELETE operations. (b) ADD operations. We also evaluated the memory requirements for dynamic updating. We only measured the memory consumption for the DELETE operation, because the ADD operation is essentially reduced to an edge removal operation. Tables 2-6 show the memory usage comparison between the ab initio computation and the dynamic updating, which were averaged over 10 operations. In each table, the first column contains the % of the dataset being considered, the second column presents the memory usage for the ab initio computation, the third column presents the memory usage for the dynamic updating, and the fourth column presents the memory ratio between dynamic updating and ab initio computation. As an illustrative baseline, Figure 23 shows the memory usage for the _Yersinia.wgMLST_ dataset as an increasing percentage of it added to the computation. Given these results, we can observe that both the ab initio computation and the dynamic updating required linear space regarding the size of the input. This is also consistent with the results for random graphs presented above.