1 Search Results for "Nikolopoulos, Stavros D."

Document
DOI: 10.4230/LIPIcs.SEA.2022.14
An Experimental Study of Algorithms for Packing Arborescences

Authors: Loukas Georgiadis, Dionysios Kefallinos, Anna Mpanti, and Stavros D. Nikolopoulos

Published in: LIPIcs, Volume 233, 20th International Symposium on Experimental Algorithms (SEA 2022)

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.
Cite as

Loukas Georgiadis, Dionysios Kefallinos, Anna Mpanti, and Stavros D. Nikolopoulos. An Experimental Study of Algorithms for Packing Arborescences. In 20th International Symposium on Experimental Algorithms (SEA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 233, pp. 14:1-14:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2022.14},
  URN =		{urn:nbn:de:0030-drops-165480},
  doi =		{10.4230/LIPIcs.SEA.2022.14},
  annote =	{Keywords: Arborescences, Edge Connectivity, Graph Algorithms}
}
  • Refine by Author
  • 1 Georgiadis, Loukas
  • 1 Kefallinos, Dionysios
  • 1 Mpanti, Anna
  • 1 Nikolopoulos, Stavros D.

  • Refine by Classification
  • 1 Mathematics of computing → Graph algorithms
  • 1 Theory of computation → Graph algorithms analysis

  • Refine by Keyword
  • 1 Arborescences
  • 1 Edge Connectivity
  • 1 Graph Algorithms

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2022

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact