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.2021.23
URN: urn:nbn:de:0030-drops-137958
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/13795/
Brodal, Gerth Stølting ;
Fagerberg, Rolf ;
Hammer, David ;
Meyer, Ulrich ;
Penschuck, Manuel ;
Tran, Hung
An Experimental Study of External Memory Algorithms for Connected Components
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.
BibTeX - Entry
@InProceedings{brodal_et_al:LIPIcs.SEA.2021.23,
author = {Brodal, Gerth St{\o}lting and Fagerberg, Rolf and Hammer, David and Meyer, Ulrich and Penschuck, Manuel and Tran, Hung},
title = {{An Experimental Study of External Memory Algorithms for Connected Components}},
booktitle = {19th International Symposium on Experimental Algorithms (SEA 2021)},
pages = {23:1--23:23},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-185-6},
ISSN = {1868-8969},
year = {2021},
volume = {190},
editor = {Coudert, David and Natale, Emanuele},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/13795},
URN = {urn:nbn:de:0030-drops-137958},
doi = {10.4230/LIPIcs.SEA.2021.23},
annote = {Keywords: Connected Components, Experimental Evaluation, External Memory, Graph Algorithms, Randomization}
}
