Document Open Access Logo

An Upper Bound on the Number of Extreme Shortest Paths in Arbitrary Dimensions

Authors Florian Barth , Stefan Funke, Claudius Proissl

PDF
Thumbnail PDF

File

LIPIcs.ESA.2022.14.pdf
  • Filesize: 0.87 MB
  • 12 pages

Document Identifiers

Author Details

Florian Barth
  • Universität Stuttgart, Germany
Stefan Funke
  • Universität Stuttgart, Germany
Claudius Proissl
  • Universität Stuttgart, Germany

Funding

This work was in part supported by the Deutsche Forschungsgemeinschaft (DFG) within the priority program 1894: Volunteered Geographic Information: Interpretation, Visualization and Social Computing.

Acknowledgements

We thank Kshitij Gajjar and Jaikumar Radhakrishnan for their very helpful input and for identifying an error in a previous version of this paper.

Cite AsGet BibTex

Florian Barth, Stefan Funke, and Claudius Proissl. An Upper Bound on the Number of Extreme Shortest Paths in Arbitrary Dimensions. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 14:1-14:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.ESA.2022.14

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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Shortest paths
Keywords
  • Parametric Shortest Paths
  • Extreme Shortest Paths

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Florian Barth, Stefan Funke, and Claudius Proissl. Preference-based trajectory clustering: An application of geometric hitting sets. In 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2021. Google Scholar
  2. Florian Barth, Stefan Funke, and Sabine Storandt. Alternative multicriteria routes. In 2019 Proceedings of the Meeting on Algorithm Engineering and Experiments (ALENEX), pages 66-80, 2019. URL: https://doi.org/10.1137/1.9781611975499.6.
  3. HP Benson and E Sun. Outcome space partition of the weight set in multiobjective linear programming. Journal of Optimization Theory and Applications, 105(1):17-36, 2000. Google Scholar
  4. Jon Louis Bentley, Hsiang-Tsung Kung, Mario Schkolnick, and Clark D. Thompson. On the average number of maxima in a set of vectors and applications. J. ACM, 25(4):536-543, October 1978. URL: https://doi.org/10.1145/322092.322095.
  5. Patricia J Carstensen. Complexity of some parametric integer and network programming problems. Mathematical Programming, 26(1):64-75, 1983. Google Scholar
  6. Patricia June Carstensen. The complexity of some problems in parametric linear and combinatorial programming. PhD thesis, University of Michigan, 1983. Google Scholar
  7. Daniel Delling and Dorothea Wagner. Pareto paths with SHARC. In Proc. 8th International Symposium on Experimental Algorithms (SEA), volume 5526 of Lecture Notes in Computer Science, pages 125-136. Springer, 2009. Google Scholar
  8. Stefan Funke and Sabine Storandt. Personalized route planning in road networks. In Proc. 23rd SIGSPATIAL International Conference on Advances in Geographic Information Systems, Bellevue, WA, USA, pages 45:1-45:10. ACM, 2015. Google Scholar
  9. Kshitij Gajjar and Jaikumar Radhakrishnan. Parametric shortest paths in planar graphs. In 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS), pages 876-895. IEEE, 2019. Google Scholar
  10. Robert Geisberger, Moritz Kobitzsch, and Peter Sanders. Route planning with flexible objective functions. In Workshop on Algorithms and Experimentation, ALENEX '10, pages 124-137, USA, 2010. Society for Industrial and Applied Mathematics. Google Scholar
  11. Daniel Mier Gusfield. Sensitivity analysis for combinatorial optimization. PhD thesis, University of California, Berkeley, 1980. Google Scholar
  12. Gabriel Y Handler and Israel Zang. A dual algorithm for the constrained shortest path problem. Networks, 10(4):293-309, 1980. Google Scholar
  13. Hans-Peter Kriegel, Matthias Renz, and Matthias Schubert. Route skyline queries: A multi-preference path planning approach. In 26th International Conference on Data Engineering (ICDE), pages 261-272. IEEE Computer Society, 2010. Google Scholar
  14. Kurt Mehlhorn and Mark Ziegelmann. Resource constrained shortest paths. In European Symposium on Algorithms, pages 326-337. Springer, 2000. Google Scholar
  15. Ketan Mulmuley and Pradyut Shah. A lower bound for the shortest path problem. In Proceedings 15th Annual IEEE Conference on Computational Complexity, pages 14-21. IEEE, 2000. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact