License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SEA.2022.14
URN: urn:nbn:de:0030-drops-165480
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/16548/
Georgiadis, Loukas ;
Kefallinos, Dionysios ;
Mpanti, Anna ;
Nikolopoulos, Stavros D.
An Experimental Study of Algorithms for Packing Arborescences
Abstract
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.
BibTeX - Entry
@InProceedings{georgiadis_et_al:LIPIcs.SEA.2022.14,
author = {Georgiadis, Loukas and Kefallinos, Dionysios and Mpanti, Anna and Nikolopoulos, Stavros D.},
title = {{An Experimental Study of Algorithms for Packing Arborescences}},
booktitle = {20th International Symposium on Experimental Algorithms (SEA 2022)},
pages = {14:1--14:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-251-8},
ISSN = {1868-8969},
year = {2022},
volume = {233},
editor = {Schulz, Christian and U\c{c}ar, Bora},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/16548},
URN = {urn:nbn:de:0030-drops-165480},
doi = {10.4230/LIPIcs.SEA.2022.14},
annote = {Keywords: Arborescences, Edge Connectivity, Graph Algorithms}
}
