Overview Statistic: PDF-Downloads (blue) and Frontdoor-Views (gray)

A Label Setting Multiobjective Shortest Path FPTAS

  • 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.

Export metadata

Additional Services

Share in Twitter Search Google Scholar Statistics - number of accesses to the document
Author:Luitgard Kraus
Document Type:Bachelor's Thesis
CCS-Classification:J. Computer Applications
Granting Institution:Freie Universität Berlin
Advisor:Ralf Borndörfer, Niels Lindner, Pedro Maristany de las Casas
Year of first publication:2021
Accept ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.