License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2022.14
URN: urn:nbn:de:0030-drops-169525
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/16952/
Barth, Florian ;
Funke, Stefan ;
Proissl, Claudius
An Upper Bound on the Number of Extreme Shortest Paths in Arbitrary Dimensions
Abstract
Graphs with multiple edge costs arise naturally in the route planning domain when apart from travel time other criteria like fuel consumption or positive height difference are also objectives to be minimized. In such a scenario, this paper investigates the number of extreme shortest paths between a given source-target pair s, t. We show that for a fixed but arbitrary number of cost types d ≥ 1 the number of extreme shortest paths is in n^O(log^{d-1}n) in graphs G with n nodes. This is a generalization of known upper bounds for d = 2 and d = 3.
BibTeX - Entry
@InProceedings{barth_et_al:LIPIcs.ESA.2022.14,
author = {Barth, Florian and Funke, Stefan and Proissl, Claudius},
title = {{An Upper Bound on the Number of Extreme Shortest Paths in Arbitrary Dimensions}},
booktitle = {30th Annual European Symposium on Algorithms (ESA 2022)},
pages = {14:1--14:12},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-247-1},
ISSN = {1868-8969},
year = {2022},
volume = {244},
editor = {Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva and Herman, Grzegorz},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/16952},
URN = {urn:nbn:de:0030-drops-169525},
doi = {10.4230/LIPIcs.ESA.2022.14},
annote = {Keywords: Parametric Shortest Paths, Extreme Shortest Paths}
}
|
Keywords: |
|
Parametric Shortest Paths, Extreme Shortest Paths |
|
Collection: |
|
30th Annual European Symposium on Algorithms (ESA 2022) |
|
Issue Date: |
|
2022 |
|
Date of publication: |
|
01.09.2022 |
