Projects per year
Abstract
Vertex connectivity is a wellstudied concept in graph theory with numerous applications. A graph is kconnected 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 kconnected. There is a long history of algorithmic development for efficiently computing vertex connectivity. Recently, two near lineartime algorithms for small k were introduced by Forster et al. [SODA 2020]. Prior to that, the bestknown 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 spaceefficiency (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 realworld graphs with vertex connectivity between 4 and 8, the degree counting heuristic offers a factor of 2–4 speedup over the original nondegree counting version for small graphs and almost 20 times for some graphs with millions of edges. It also outperforms the previous stateoftheart algorithm by Henzinger et al., even on relatively small graphs.
Original language  English 

Article number  4.4 
Pages (fromto)  129 
Number of pages  29 
Journal  ACM Journal of Experimental Algorithmics 
Volume  27 
DOIs  
Publication status  Published  13 Dec 2022 
MoE publication type  A1 Journal articlerefereed 
Keywords
 sublinear algorithms
 Algorithm 
 engineering
 algorithmic graph theory
Fingerprint
Dive into the research topics of 'Engineering Nearly LinearTime Algorithms for Small Vertex Connectivity'. Together they form a unique fingerprint.Projects
 1 Active

ALGOCom: Novel Algorithmic Techniques through the Lens of Combinatorics
Chalermsook, P., Jindal, G., Franck, M., Spoerhase, J., Yingchareonthawornchai, S., Gadekar, A., Orgo, L., Jiamjitrak, W. & Khodamoradi, K.
01/02/2018 → 31/01/2024
Project: EU: ERC grants
Press/Media

Aalto University Researcher Releases New Data on Algorithms (Engineering Nearly Lineartime Algorithms for Small Vertex Connectivity)
Sorrachai Yingchareonthawornchai
03/01/2023
1 item of Media coverage
Press/Media: Media appearance