2026-07-23T04:16:35Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:16548 2024-03-06T10:57:46Z ddc:004 open_access

An Experimental Study of Algorithms for Packing Arborescences Georgiadis, Loukas Kefallinos, Dionysios Mpanti, Anna Nikolopoulos, Stavros D. Arborescences Edge Connectivity Graph Algorithms A classic result of Edmonds states that the maximum number of edge-disjoint arborescences of a directed graph G, rooted at a designated vertex s, equals the minimum cardinality c_G(s) of an s-cut of G. This concept is related to the edge connectivity λ(G) of a strongly connected directed graph G, defined as the minimum number of edges whose deletion leaves a graph that is not strongly connected. In this paper, we address the question of how efficiently we can compute a maximum packing of edge-disjoint arborescences in practice, compared to the time required to determine the edge connectivity of a graph. To that end, we explore the design space of efficient algorithms for packing arborescences of a directed graph in practice and conduct a thorough empirical study to highlight the merits and weaknesses of each technique. In particular, we present an efficient implementation of Gabow’s arborescence packing algorithm and provide a simple but efficient heuristic that significantly improves its running time in practice. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Loukas Georgiadis and Dionysios Kefallinos and Anna Mpanti and Stavros D. Nikolopoulos 2022 Is Part Of LIPIcs, Volume 233, 20th International Symposium on Experimental Algorithms (SEA 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SEA.2022.14 urn:nbn:de:0030-drops-165480 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2022.14 eng https://creativecommons.org/licenses/by/4.0/legalcode