Department of Computer Science: MSc Thesis Presentation
Max Franck will present his MSc thesis "An Experimental Study of a Near-Linear Time Algorithm for Small Vertex Connectivity" on Friday 30 October at 14:00 via Zoom.
![MSc_thesis_CS](/sites/g/files/flghsv161/files/styles/1_300w_300h_n/public/2019-01/msc.png?h=d1cb525d&itok=s4fnixFX)
When
–
Where
Event language(s)
English
An Experimental Study of a Near-Linear Time Algorithm for Small Vertex Connectivity
Author: Max Franck
Supervisor: Professor Parinya Chalermsook
Date: Friday 30 October 2020
Time: 14:00
Zoom: https://aalto.zoom.us/j/61499916759
Short description: 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.