KIT | KIT-Bibliothek | Impressum | Datenschutz

Efficiently Computing Directed Minimum Spanning Trees

Böther, M.; Kißig, O.; Weyand, Christopher ORCID iD icon 1
1 Institut für Theoretische Informatik (ITI), Karlsruher Institut für Technologie (KIT)

Abstract:

Computing a directed minimum spanning tree, called arborescence, is a fundamental algorithmic problem, although not as common as its undirected counterpart. In 1967, Edmonds discussed an elegant solution. It was refined to run in O(min(n$^2$,m log n)) by Tarjan which is optimal for very dense and very sparse graphs. Gabow et al. gave a version of Edmonds' algorithm that runs in O(n log n + m), thus asymptotically beating the Tarjan variant in the regime between sparse and dense. Despite the attention the problem received theoretically, there exists, to the best of our knowledge, no empirical evaluation of either of these algorithms. In fact, the version by Gabow et al. has never been implemented and, aside from coding competitions, all readily available Tarjan implementations run in O(n$^2$). In this paper, we provide the first implementation of the version by Gabow et al. as well as five variants of Tarjan's version with different underlying data structures. We evaluate these algorithms and existing solvers on a large set of real-world and random graphs.


Download
Originalveröffentlichung
DOI: 10.1137/1.9781611977561.ch8
Scopus
Zitationen: 2
Zugehörige Institution(en) am KIT Institut für Theoretische Informatik (ITI)
Publikationstyp Proceedingsbeitrag
Publikationsjahr 2023
Sprache Englisch
Identifikator ISBN: 978-1-61197-756-1
ISSN: 2164-0300
KITopen-ID: 1000158034
Erschienen in 2023 Proceedings of the Symposium on Algorithm Engineering and Experiments (ALENEX)
Veranstaltung SIAM Symposium on Algorithm Engineering and Experiments (ALENEX 2023), Florenz, Italien, 22.01.2023 – 23.01.2023
Verlag Society for Industrial and Applied Mathematics (SIAM)
Seiten 86-95
Serie Proceedings of the 2023 Workshop on Algorithm Engineering and Experiments
Nachgewiesen in Scopus
Relationen in KITopen
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page