Tietotekniikan laitoksen diplomityöesitelmä

An Experimental Study of a Near-Linear Time Algorithm for Small Vertex Connectivity

Diplomityöntekijä: Max Franck
Ohjaaja: Professor Parinya Chalermsook

Aika: Perjantai 30.10. klo 14
Zoom: https://aalto.zoom.us/j/61499916759

Lyhyt kuvaus (englanniksi): This thesis studies the practical performance of a recently discovered near-linear time algorithm for small vertex connectivity (https://arxiv.org/abs/1910.14344) in comparison to the previous state-of-the-art, which has quadratic time complexity. The experiments focus on undirected graphs. The results suggest that the new algorithm is fast in practice. Novel variations are also explored for the near-linear time algorithm, further improving practical performance.