Engineering Nearly Linear-Time Algorithms for Small Vertex Connectivity

Loading...
Thumbnail Image
Access rights
openAccess
Journal Title
Journal ISSN
Volume Title
A1 Alkuperäisartikkeli tieteellisessä aikakauslehdessä
This publication is imported from Aalto University research portal.
View publication in the Research portal
View/Open full text file from the Research portal
Date
2022-12-13
Major/Subject
Mcode
Degree programme
Language
en
Pages
29
1-29
Series
ACM Journal of Experimental Algorithmics, Volume 27
Abstract
Vertex connectivity is a well-studied concept in graph theory with numerous applications. A graph is k-connected if it remains connected after removing any k −1 vertices. The vertex connectivity of a graph is the maximum k such that the graph is k-connected. There is a long history of algorithmic development for efficiently computing vertex connectivity. Recently, two near linear-time algorithms for small k were introduced by Forster et al. [SODA 2020]. Prior to that, the best-known algorithm was one by Henzinger et al. [FOCS 1996] with quadratic running time when k is small.In this article, we study the practical performance of the algorithms by Forster et al. In addition, we introduce a new heuristic on a key subroutine called local cut detection, which we call degree counting. We prove that the new heuristic improves space-efficiency (which can be good for caching purposes) and allows the subroutine to terminate earlier. According to experimental results on random graphs with planted vertex cuts, random hyperbolic graphs, and real-world graphs with vertex connectivity between 4 and 8, the degree counting heuristic offers a factor of 2–4 speedup over the original non-degree counting version for small graphs and almost 20 times for some graphs with millions of edges. It also outperforms the previous state-of-the-art algorithm by Henzinger et al., even on relatively small graphs.
Description
| openaire: EC/H2020/759557/EU//ALGOCom
Keywords
sublinear algorithms, Algorithm&nbsp, engineering, algorithmic graph theory
Other note
Citation
Franck , M & Yingchareonthawornchai , S 2022 , ' Engineering Nearly Linear-Time Algorithms for Small Vertex Connectivity ' , ACM Journal of Experimental Algorithmics , vol. 27 , 4.4 , pp. 1-29 . https://doi.org/10.1145/3564822