Projekteja vuodessa
Abstrakti
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.
Alkuperäiskieli  Englanti 

Artikkeli  4.4 
Sivut  129 
Sivumäärä  29 
Julkaisu  ACM Journal of Experimental Algorithmics 
Vuosikerta  27 
DOI  pysyväislinkit  
Tila  Julkaistu  13 jouluk. 2022 
OKMjulkaisutyyppi  A1 Julkaistu artikkeli, soviteltu 
Sormenjälki
Sukella tutkimusaiheisiin 'Engineering Nearly LinearTime Algorithms for Small Vertex Connectivity'. Ne muodostavat yhdessä ainutlaatuisen sormenjäljen.Projektit
 1 Aktiivinen

ALGOCom (ERC)
Chalermsook, P., Jindal, G., Franck, M., Spoerhase, J., Jiamjitrak, W., Khodamoradi, K., Yingchareonthawornchai, S., Gadekar, A. & Orgo, L.
01/02/2018 → 31/01/2024
Projekti: EU: ERC grants
Lehtileikkeet

Aalto University Researcher Releases New Data on Algorithms (Engineering Nearly Lineartime Algorithms for Small Vertex Connectivity)
Sorrachai Yingchareonthawornchai
03/01/2023
1 kohde/ Medianäkyvyys
Lehdistö/media: Esiintyminen mediassa