–
November 22, 2021
Talk 1
Speaker
Ali Al Zoobi (COATI)
Title
Practical computation of simple paths with length and diversity constraints in complex and multimodal networks
Abstract
The shortest path problem is one of the most studied problem in graph theory and operations research. A classic generalization of this problem is the problem of finding k shortest simple paths (kSSP for short). That is, the problem of finding a shortest, a second-shortest, etc. until a k-th shortest simple path from a source to a destination in a directed weighted graph. Yen (1971) proposed the state-of-the-art kSSP algorithm, with theoretical time complexity in O(kn(m+nlogn)), where n is the number of vertices and m is the number of arcs of the input digraph. Since then, the problem has been widely studied from an algorithmic engineering perspective, that is designing exact algorithms offering better performances in practice.
In this thesis, we study the kSSP problem from an algorithm engineering perspective.
More precisely, we design new kSSP algorithms allowing to outperform the state-of-the-art algorithms in terms of running time, memory consumption, or offering a better space-time trade-off. We also show how to apply our algorithms in graphs with arbitrary arc weights without negative cycles. Then, we study the problem of finding paths respecting dissimilarity constraints. Precisely, we study the complexity of the problem according to four different similarity measures, and we show in which cases the problem is NP-Complete or polynomial time solvable. Finally, we show how to adapt the kSSP problem to a multimodal public transportation network model, i.e., combining metro, tram, buses, and walk. Precisely, we design some kSSP algorithms to solve a related problem, which is, the problem of finding k earliest arrival journeys from a source station to a destination station in a public multimodal transportation network.
