TY - THES
A1 - Kraus, Luitgard
T1 - A Label Setting Multiobjective Shortest Path FPTAS
N2 - Algorithms that solve the shortest path problem can largely be split into the two categories of label setting and label correcting. The Multiobjective Shortest Path (MOSP) problem is a generalization of the classical shortest path problem in terms of the dimension of the cost function. We explore the differences of two similar MOSP label setting algorithms. Furthermore, we present and prove a general method of how to derive Fully Polynomial Time Approximation Schemes (FPTAS) for MOSP label setting algorithms. Finally, we explore two pruning techniques for the one to one variants of exact label setting MOSP algorithms and adapt them to their FPTAS variants.
Y1 - 2021
UR - https://opus4.kobv.de/opus4-zib/frontdoor/index/index/docId/8415
ER -