Seminars and Events at automatic control
All seminars are held at the Department of Automatic Control, in the seminar room M 3170-73 on the third floor in the M-building, unless stated otherwise.
Master thesis presentation by Lennart Küssner: On The Fully Dynamic All-Pairs Shortest Path Problem In Sparse Digraphs
Disputation
From:
2025-06-03 10:15
to
11:00
Place: Seminar Room M 3170-73 in the M-building, LTH
Contact: emma [dot] tegling [at] control [dot] lth [dot] se
Date & Time: June 3th, 10:15-11:00
Location: Seminar Room M 3170-73 in the M-building, LTH
Author: Lennart Küssner
Title: On The Fully Dynamic All-Pairs Shortest Path Problem In Sparse Digraphs
Supervisor: Maximilian Probst Gutenberg, Tianyi Zhang (ETH Zürich), Giacomo Como (LTH)
Examiner: Emma Tegling
Abstract: The All Pairs Shortest Path (APSP) problem involves finding weighted shortest paths between all vertex pairs in a graph. It has been widely studied in both dense and sparse graphs. Real-world networks, often sparse, frequently change over time—e.g. due to traffic events in the case of a road network—motivating the study of fully dynamic APSP in sparse graphs, where what was known about shortest paths before a small perturbation is used to quickly recompute the new shortest paths.
This thesis explores applying recent dense-graph techniques to sparse APSP. The first result shows these methods cannot improve sparse APSP due to their reliance on iterating over all vertex pairs, which remains inherently dense. The second contribution introduces a new algorithm, unrelated to the dense techniques, offering a trade-off between update and query times (ignoring polylog factors): O(mn^2/t^(3/2)) and O(t) for t in [n^(2/3), n^(8/9)], achieving an improved update time of O(mn^(2/3)).