On Fully Dynamic All Pairs Shortest Path in Sparse Digraphs
(2025)Department of Automatic Control
- Abstract
- The All Pairs Shortest Path (APSP) problem is ubiquitous in computer science. The problem consists of finding for any vertex pair, the weighted shortest paths in a network with real-weighted edges. The problem has been studied thoroughly, both for dense graphs, where the number of edges can be quadratic in the number of vertices, and for sparse graphs, where the number of edges is considerably lower than so.
Many real world networks are subject to small changes over time. For instance, road work or traffic accidents can considerably change the shortest paths through a road network. As most real world networks are also sparse, this motivates the study of the sparse fully dynamic APSP problem, where a data stucture is maintained for a... (More) - The All Pairs Shortest Path (APSP) problem is ubiquitous in computer science. The problem consists of finding for any vertex pair, the weighted shortest paths in a network with real-weighted edges. The problem has been studied thoroughly, both for dense graphs, where the number of edges can be quadratic in the number of vertices, and for sparse graphs, where the number of edges is considerably lower than so.
Many real world networks are subject to small changes over time. For instance, road work or traffic accidents can considerably change the shortest paths through a road network. As most real world networks are also sparse, this motivates the study of the sparse fully dynamic APSP problem, where a data stucture is maintained for a sparse graph subject to vertex insertions and deletions, from which the shortest path between any pair of vertices should be quickly queryable.
This thesis comes with two main results: Firstly, the key methods that led to the improvement in the dense case have been studied to determine whether they can be applied in the sparse case. Conclusively it has been shown that the techniques studied rely on subroutines that iterate through all vertex pairs, with no real possibility to change this. Therefore, they cannot be transferred to the sparse case to give an algorithm with update time subquadratic in the number of vertices. Given this, no improvement over the state of the art in the sparse case is possible using the new dense methods.
Secondly, a novel algorithm with a trade-off between the update and query time of ˜O (mn2/t3/2), ˜O(t) for t ∈ [n2/3,n8/9] is presented, making it possible to reach an update time of ˜O(mn2/3), improving over the state of the art. (Less)
Please use this url to cite or link to this publication:
http://lup.lub.lu.se/student-papers/record/9205998
- author
- Küssner, Lennart
- supervisor
-
- Giacomo Como LU
- Emma Tegling LU
- organization
- year
- 2025
- type
- H3 - Professional qualifications (4 Years - )
- subject
- report number
- TFRT-6275
- other publication id
- 0280-5316
- language
- English
- id
- 9205998
- date added to LUP
- 2025-08-08 15:12:21
- date last changed
- 2025-08-08 15:12:21
@misc{9205998,
abstract = {{The All Pairs Shortest Path (APSP) problem is ubiquitous in computer science. The problem consists of finding for any vertex pair, the weighted shortest paths in a network with real-weighted edges. The problem has been studied thoroughly, both for dense graphs, where the number of edges can be quadratic in the number of vertices, and for sparse graphs, where the number of edges is considerably lower than so.
Many real world networks are subject to small changes over time. For instance, road work or traffic accidents can considerably change the shortest paths through a road network. As most real world networks are also sparse, this motivates the study of the sparse fully dynamic APSP problem, where a data stucture is maintained for a sparse graph subject to vertex insertions and deletions, from which the shortest path between any pair of vertices should be quickly queryable.
This thesis comes with two main results: Firstly, the key methods that led to the improvement in the dense case have been studied to determine whether they can be applied in the sparse case. Conclusively it has been shown that the techniques studied rely on subroutines that iterate through all vertex pairs, with no real possibility to change this. Therefore, they cannot be transferred to the sparse case to give an algorithm with update time subquadratic in the number of vertices. Given this, no improvement over the state of the art in the sparse case is possible using the new dense methods.
Secondly, a novel algorithm with a trade-off between the update and query time of ˜O (mn2/t3/2), ˜O(t) for t ∈ [n2/3,n8/9] is presented, making it possible to reach an update time of ˜O(mn2/3), improving over the state of the art.}},
author = {{Küssner, Lennart}},
language = {{eng}},
note = {{Student Paper}},
title = {{On Fully Dynamic All Pairs Shortest Path in Sparse Digraphs}},
year = {{2025}},
}