{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,12,7]],"date-time":"2023-12-07T00:51:48Z","timestamp":1701910308256},"reference-count":36,"publisher":"MDPI AG","issue":"12","license":[{"start":{"date-parts":[[2023,12,6]],"date-time":"2023-12-06T00:00:00Z","timestamp":1701820800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"Let G=(V,E) be a directed and weighted graph with a vertex set V of size n and an edge set E of size m such that each edge (u,v)\u2208E has a real-valued weight w(u,c). An arborescence in G is a subgraph T=(V,E\u2032) such that, for a vertex u\u2208V, which is the root, there is a unique path in T from u to any other vertex v\u2208V. The weight of T is the sum of the weights of its edges. In this paper, given G, we are interested in finding an arborescence in G with a minimum weight, i.e., an optimal arborescence. Furthermore, when G is subject to changes, namely, edge insertions and deletions, we are interested in efficiently maintaining a dynamic arborescence in G. This is a well-known problem with applications in several domains such as network design optimization and phylogenetic inference. In this paper, we revisit the algorithmic ideas proposed by several authors for this problem. We provide detailed pseudocode, as well as implementation details, and we present experimental results regarding large scale-free networks and phylogenetic inference. Our implementation is publicly available.<\/jats:p>","DOI":"10.3390\/a16120559","type":"journal-article","created":{"date-parts":[[2023,12,6]],"date-time":"2023-12-06T13:48:32Z","timestamp":1701870512000},"page":"559","source":"Crossref","is-referenced-by-count":0,"title":["On Finding Optimal (Dynamic) Arborescences"],"prefix":"10.3390","volume":"16","author":[{"given":"Joaquim","family":"Espada","sequence":"first","affiliation":[{"name":"Instituto de Engenharia de Sistemas e Computadores, Investiga\u00e7\u00e3o e Desenvolvimento em Lisboa (INESC-ID), 1000-029 Lisboa, Portugal"},{"name":"Instituto Superior T\u00e9cnico, Universidade de Lisboa, 1049-001 Lisboa, Portugal"}]},{"ORCID":"http:\/\/orcid.org\/0000-0003-4852-1641","authenticated-orcid":false,"given":"Alexandre P.","family":"Francisco","sequence":"additional","affiliation":[{"name":"Instituto de Engenharia de Sistemas e Computadores, Investiga\u00e7\u00e3o e Desenvolvimento em Lisboa (INESC-ID), 1000-029 Lisboa, Portugal"},{"name":"Instituto Superior T\u00e9cnico, Universidade de Lisboa, 1049-001 Lisboa, Portugal"}]},{"given":"Tatiana","family":"Rocher","sequence":"additional","affiliation":[{"name":"Instituto de Engenharia de Sistemas e Computadores, Investiga\u00e7\u00e3o e Desenvolvimento em Lisboa (INESC-ID), 1000-029 Lisboa, Portugal"}]},{"given":"Lu\u00eds M. S.","family":"Russo","sequence":"additional","affiliation":[{"name":"Instituto de Engenharia de Sistemas e Computadores, Investiga\u00e7\u00e3o e Desenvolvimento em Lisboa (INESC-ID), 1000-029 Lisboa, Portugal"},{"name":"Instituto Superior T\u00e9cnico, Universidade de Lisboa, 1049-001 Lisboa, Portugal"}]},{"given":"C\u00e1tia","family":"Vaz","sequence":"additional","affiliation":[{"name":"Instituto de Engenharia de Sistemas e Computadores, Investiga\u00e7\u00e3o e Desenvolvimento em Lisboa (INESC-ID), 1000-029 Lisboa, Portugal"},{"name":"Instituto Superior de Engenharia de Lisboa, Instituto Polit\u00e9cnico de Lisboa, 1959-007 Lisboa, Portugal"}]}],"member":"1968","published-online":{"date-parts":[[2023,12,6]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"1460","DOI":"10.1109\/TMC.2006.154","article-title":"On the construction of a strongly connected broadcast arborescence with bounded transmission delay","volume":"5","author":"Li","year":"2006","journal-title":"IEEE Trans. Mob. Comput."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"114","DOI":"10.1016\/j.dam.2016.07.015","article-title":"Optimal design of switched Ethernet networks implementing the Multiple Spanning Tree Protocol","volume":"234","author":"Fortz","year":"2018","journal-title":"Discrete Appl. Math."},{"key":"ref_3","unstructured":"Gerhard, R. (1994). The Traveling Salesman: Computational Solutions for TSP Applications, Springer. Lecture Notes in Computer Science."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"24","DOI":"10.1109\/43.673630","article-title":"Efficient algorithms for the minimum shortest path Steiner arborescence problem with applications to VLSI physical design","volume":"17","author":"Cong","year":"1998","journal-title":"IEEE Trans. Comput. Aided Des. Integr. Circuits Syst."},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Coscia, M. (2018). Using arborescences to estimate hierarchicalness in directed complex networks. PLoS ONE, 13.","DOI":"10.1371\/journal.pone.0190825"},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"1395","DOI":"10.1101\/gr.232397.117","article-title":"GrapeTree: Visualization of core genomic relationships among 100,000 bacterial pathogens","volume":"28","author":"Zhou","year":"2018","journal-title":"Genome Res."},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Vaz, C., Nascimento, M., Carri\u00e7o, J.A., Rocher, T., and Francisco, A.P. (2021). Distance-based phylogenetic inference from typing data: A unifying view. Brief. Bioinform., 22.","DOI":"10.1093\/bib\/bbaa147"},{"key":"ref_8","first-page":"1396","article-title":"On the shortest arborescence of a directed graph","volume":"14","author":"Chu","year":"1965","journal-title":"Sci. Sin."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"233","DOI":"10.6028\/jres.071B.032","article-title":"Optimum branchings","volume":"71","author":"Edmonds","year":"1967","journal-title":"J. Res. Natl. Bur. Stand. B"},{"key":"ref_10","first-page":"29","article-title":"An algorithm to construct a minimum directed spanning tree in a directed network","volume":"29","author":"Bock","year":"1971","journal-title":"Dev. Oper. Res."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1002\/net.3230070103","article-title":"Finding optimum branchings","volume":"7","author":"Tarjan","year":"1977","journal-title":"Networks"},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"309","DOI":"10.1002\/net.3230090403","article-title":"A note on finding optimum branchings","volume":"9","author":"Camerini","year":"1979","journal-title":"Networks"},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1007\/BF02579168","article-title":"Efficient algorithms for finding minimum spanning trees in undirected and directed graphs","volume":"6","author":"Gabow","year":"1986","journal-title":"Combinatorica"},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"426","DOI":"10.1287\/ijoc.5.4.426","article-title":"An efficient algorithm for the min-sum arborescence problem on complete digraphs","volume":"5","author":"Fischetti","year":"1993","journal-title":"ORSA J. Comput."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1145\/262301.262309","article-title":"Emerging opportunities for theoretical computer science","volume":"28","author":"Aho","year":"1997","journal-title":"ACM SIGACT News"},{"key":"ref_16","unstructured":"Sanders, P. (2009). Efficient Algorithms, Springer."},{"key":"ref_17","unstructured":"Tofigh, A., and Sj\u00f6lund, E. (2023, November 04). Implementation of Edmonds\u2019s Optimum Branching Algorithm. Available online: https:\/\/github.com\/atofigh\/edmonds-alg\/."},{"key":"ref_18","unstructured":"Hagberg, A., Schult, D., and Swart, P. (2023, November 04). NetworkX. Available online: https:\/\/networkx.org\/documentation\/stable\/reference\/algorithms\/."},{"key":"ref_19","unstructured":"Espada, J. (2019). Large Scale Phylogenetic Inference from Noisy Data Based on Minimum Weight Spanning Arborescences. [Master\u2019s Thesis, IST, Universidade de Lisboa]."},{"key":"ref_20","doi-asserted-by":"crossref","unstructured":"B\u00f6ther, M., Ki\u00dfig, O., and Weyand, C. (2023, January 22\u201323). Efficiently computing directed minimum spanning trees. Proceedings of the 2023 Symposium on Algorithm Engineering and Experiments (ALENEX), Florence, Italy.","DOI":"10.1137\/1.9781611977561.ch8"},{"key":"ref_21","doi-asserted-by":"crossref","unstructured":"Pollatos, G.G., Telelis, O.A., and Zissimopoulos, V. (2006, January 24\u201327). Updating directed minimum cost spanning trees. Proceedings of the International Workshop on Experimental and Efficient Algorithms, Menorca, Spain.","DOI":"10.1007\/11764298_27"},{"key":"ref_22","unstructured":"Barab\u00e1si, A.L. (2016). Network Science, Cambridge University Press."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"301","DOI":"10.1145\/364099.364331","article-title":"An improved equivalence algorithm","volume":"7","author":"Galler","year":"1964","journal-title":"Commun. ACM"},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"245","DOI":"10.1145\/62.2160","article-title":"Worst-case analysis of set union algorithms","volume":"31","author":"Tarjan","year":"1984","journal-title":"J. ACM (JACM)"},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"347","DOI":"10.1145\/512274.512284","article-title":"Algorithm 232: Heapsort","volume":"7","author":"Williams","year":"1964","journal-title":"Commun. ACM"},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"309","DOI":"10.1145\/359460.359478","article-title":"A data structure for manipulating priority queues","volume":"21","author":"Vuillemin","year":"1978","journal-title":"Commun. ACM"},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1007\/BF01840439","article-title":"The pairing heap: A new form of self-adjusting heap","volume":"1","author":"Fredman","year":"1986","journal-title":"Algorithmica"},{"key":"ref_28","unstructured":"Pettie, S. (2005, January 23\u201325). Towards a final analysis of pairing heaps. Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS\u201905), Pittsburgh, PA, USA."},{"key":"ref_29","doi-asserted-by":"crossref","unstructured":"Larkin, D.H., Sen, S., and Tarjan, R.E. (2014, January 5). A back-to-basics empirical study of priority queues. Proceedings of the 2014 Sixteenth Workshop on Algorithm Engineering and Experiments (ALENEX), Portland, OR, USA.","DOI":"10.1137\/1.9781611973198.7"},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"1141","DOI":"10.1214\/aoms\/1177706098","article-title":"Random graphs","volume":"30","author":"Gilbert","year":"1959","journal-title":"Ann. Math. Stat."},{"key":"ref_31","unstructured":"Varoquaux, G., Vaught, T., and Millman, J. (2008, January 19\u201324). Exploring Network Structure, Dynamics, and Function using NetworkX. Proceedings of the 7th Python in Science Conference, Pasadena, CA, USA."},{"key":"ref_32","unstructured":"Bollob\u00e1s, B., Borgs, C., Chayes, J.T., and Riordan, O. (2003, January 12\u201314). Directed scale-free graphs. Proceedings of the SODA, Baltimore, MD, USA."},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"677","DOI":"10.1089\/106652703322539024","article-title":"Duplication Models for Biological Networks","volume":"10","author":"Chung","year":"2003","journal-title":"J. Comput. Biol."},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"138","DOI":"10.1101\/gr.251678.119","article-title":"The EnteroBase user\u2019s guide, with case studies on Salmonella transmissions, Yersinia pestis phylogeny, and Escherichia core genomic diversity","volume":"30","author":"Zhou","year":"2020","journal-title":"Genome Res."},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"362","DOI":"10.1016\/0022-0000(83)90006-5","article-title":"A Data Structure for Dynamic Trees","volume":"26","author":"Sleator","year":"1983","journal-title":"J. Comput. Syst. Sci."},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.tcs.2018.12.020","article-title":"A study on splay trees","volume":"776","author":"Russo","year":"2019","journal-title":"Theor. Comput. Sci."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/16\/12\/559\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,12,6]],"date-time":"2023-12-06T14:03:25Z","timestamp":1701871405000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/16\/12\/559"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,12,6]]},"references-count":36,"journal-issue":{"issue":"12","published-online":{"date-parts":[[2023,12]]}},"alternative-id":["a16120559"],"URL":"https:\/\/doi.org\/10.3390\/a16120559","relation":{},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,12,6]]}}}