An experimental study of external memory algorithms for connected components

Gerth Stølting Brodal*, Rolf Fagerberg, David Hammer, Ulrich Meyer, Manuel Penschuck, Hung Tran

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

Abstract

We empirically investigate algorithms for solving Connected Components in the external memory model. In particular, we study whether the randomized O(Sort(E)) algorithm by Karger, Klein, and Tarjan can be implemented to compete with practically promising and simpler algorithms having only slightly worse theoretical cost, namely Borůvka's algorithm and the algorithm by Sibeyn and collaborators. For all algorithms, we develop and test a number of tuning options. Our experiments are executed on a large set of different graph classes including random graphs, grids, geometric graphs, and hyperbolic graphs. Among our findings are: The Sibeyn algorithm is a very strong contender due to its simplicity and due to an added degree of freedom in its internal workings when used in the Connected Components setting. With the right tunings, the Karger-Klein-Tarjan algorithm can be implemented to be competitive in many cases. Higher graph density seems to benefit Karger-Klein-Tarjan relative to Sibeyn. Borůvka's algorithm is not competitive with the two others.

Original languageEnglish
Title of host publication19th International Symposium on Experimental Algorithms, SEA 2021
EditorsDavid Coudert, Emanuele Natale
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Publication date1. Jun 2021
Pages23:1-23:23
Article number23
ISBN (Electronic)9783959771856
DOIs
Publication statusPublished - 1. Jun 2021
Event19th International Symposium on Experimental Algorithms, SEA 2021 - Virtual, Nice, France
Duration: 7. Jun 20219. Jun 2021

Conference

Conference19th International Symposium on Experimental Algorithms, SEA 2021
Country/TerritoryFrance
CityVirtual, Nice
Period07/06/202109/06/2021
SeriesLeibniz International Proceedings in Informatics, LIPIcs
Volume190
ISSN1868-8969

Bibliographical note

Publisher Copyright:
© Gerth Stølting Brodal, Rolf Fagerberg, David Hammer, Ulrich Meyer, Manuel Penschuck, and Hung Tran; licensed under Creative Commons License CC-BY 4.0 19th International Symposium on Experimental Algorithms (SEA 2021).

Keywords

  • Connected components
  • Experimental evaluation
  • External memory
  • Graph algorithms
  • Randomization

Fingerprint

Dive into the research topics of 'An experimental study of external memory algorithms for connected components'. Together they form a unique fingerprint.

Cite this