Aarhus University Seal

Dansk

You are here: » An experimental study of external memory algorithms for c...

About Aarhus University

An experimental study of external memory algorithms for connected components

Research output: Contribution to book/anthology/report/proceeding › Article in proceedings › Research › peer-review

Standard

An experimental study of external memory algorithms for connected components. / Brodal, Gerth Stølting; Fagerberg, Rolf; Hammer, David et al.

19th International Symposium on Experimental Algorithms, SEA 2021. ed. / David Coudert; Emanuele Natale. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2021. p. 23 23 (Leibniz International Proceedings in Informatics, LIPIcs, Vol. 190).

Research output: Contribution to book/anthology/report/proceeding › Article in proceedings › Research › peer-review

Harvard

Brodal, GS, Fagerberg, R, Hammer, D, Meyer, U, Penschuck, M & Tran, H 2021, An experimental study of external memory algorithms for connected components. in D Coudert & E Natale (eds), 19th International Symposium on Experimental Algorithms, SEA 2021., 23, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, Leibniz International Proceedings in Informatics, LIPIcs, vol. 190, pp. 23, 19th International Symposium on Experimental Algorithms, SEA 2021, Virtual, Nice, France, 07/06/2021. https://doi.org/10.4230/LIPIcs.SEA.2021.23

APA

Brodal, G. S., Fagerberg, R., Hammer, D., Meyer, U., Penschuck, M., & Tran, H. (2021). An experimental study of external memory algorithms for connected components. In D. Coudert, & E. Natale (Eds.), 19th International Symposium on Experimental Algorithms, SEA 2021 (pp. 23). [23] Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. Leibniz International Proceedings in Informatics, LIPIcs Vol. 190 https://doi.org/10.4230/LIPIcs.SEA.2021.23

CBE

Brodal GS, Fagerberg R, Hammer D, Meyer U, Penschuck M, Tran H. 2021. An experimental study of external memory algorithms for connected components. Coudert D, Natale E, editors. In 19th International Symposium on Experimental Algorithms, SEA 2021. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. pp. 23. (Leibniz International Proceedings in Informatics, LIPIcs, Vol. 190). https://doi.org/10.4230/LIPIcs.SEA.2021.23

MLA

Brodal, Gerth Stølting et al. "An experimental study of external memory algorithms for connected components". and Coudert, David Natale, Emanuele (editors). 19th International Symposium on Experimental Algorithms, SEA 2021. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. (Leibniz International Proceedings in Informatics, LIPIcs, Vol. 190). 2021, 23. https://doi.org/10.4230/LIPIcs.SEA.2021.23

Vancouver

Brodal GS, Fagerberg R, Hammer D, Meyer U, Penschuck M, Tran H. An experimental study of external memory algorithms for connected components. In Coudert D, Natale E, editors, 19th International Symposium on Experimental Algorithms, SEA 2021. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. 2021. p. 23. 23. (Leibniz International Proceedings in Informatics, LIPIcs, Vol. 190). doi: 10.4230/LIPIcs.SEA.2021.23

Author

Brodal, Gerth Stølting ; Fagerberg, Rolf ; Hammer, David et al. / An experimental study of external memory algorithms for connected components. 19th International Symposium on Experimental Algorithms, SEA 2021. editor / David Coudert ; Emanuele Natale. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2021. pp. 23 (Leibniz International Proceedings in Informatics, LIPIcs, Vol. 190).

Bibtex

@inproceedings{512ed81cdb0344ea9bc4f06f3d2ee5e4,
title = "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.",
keywords = "Connected components, Experimental evaluation, External memory, Graph algorithms, Randomization",
author = "Brodal, {Gerth St{\o}lting} and Rolf Fagerberg and David Hammer and Ulrich Meyer and Manuel Penschuck and Hung Tran",
note = "Publisher Copyright: {\textcopyright} Gerth St{\o}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).; 19th International Symposium on Experimental Algorithms, SEA 2021 ; Conference date: 07-06-2021 Through 09-06-2021",
year = "2021",
month = may,
doi = "10.4230/LIPIcs.SEA.2021.23",
language = "English",
series = "Leibniz International Proceedings in Informatics, LIPIcs",
publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",
pages = "23",
editor = "David Coudert and Emanuele Natale",
booktitle = "19th International Symposium on Experimental Algorithms, SEA 2021",

}

RIS

TY - GEN

T1 - An experimental study of external memory algorithms for connected components

AU - Brodal, Gerth Stølting

AU - Fagerberg, Rolf

AU - Hammer, David

AU - Meyer, Ulrich

AU - Penschuck, Manuel

AU - Tran, Hung

N1 - 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).

PY - 2021/5

Y1 - 2021/5

N2 - 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.

AB - 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.

KW - Connected components

KW - Experimental evaluation

KW - External memory

KW - Graph algorithms

KW - Randomization

UR - http://www.scopus.com/inward/record.url?scp=85108237763&partnerID=8YFLogxK

U2 - 10.4230/LIPIcs.SEA.2021.23

DO - 10.4230/LIPIcs.SEA.2021.23

M3 - Article in proceedings

AN - SCOPUS:85108237763

T3 - Leibniz International Proceedings in Informatics, LIPIcs

SP - 23

BT - 19th International Symposium on Experimental Algorithms, SEA 2021

A2 - Coudert, David

A2 - Natale, Emanuele

PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

T2 - 19th International Symposium on Experimental Algorithms, SEA 2021

Y2 - 7 June 2021 through 9 June 2021

ER -