Parametric Shortest-Path Algorithms via Tropical Geometry

Michael Joswig () and Benjamin Schröter ()
Additional contact information
Michael Joswig: Chair of Discrete Mathematics/Geometry, Technische Universität Berlin, Berlin 10623, Germany; Max Planck Institute for Mathematics in the Sciences, Leipzig 04103, Germany
Benjamin Schröter: Department of Mathematics, KTH Royal Institute of Technology, Stockholm SE-100 44, Sweden

Mathematics of Operations Research, 2022, vol. 47, issue 3, 2065-2081

Abstract: We study parameterized versions of classical algorithms for computing shortest-path trees. This is most easily expressed in terms of tropical geometry. Applications include shortest paths in traffic networks with variable link travel times.

Keywords: Primary: 14T90; secondary: 05C12; 68R10; 90B20; 90C31; parameterized shortest paths; Dijkstra’s algorithm; traffic networks; tropical geometry (search for similar items in EconPapers)
Date: 2022
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/moor.2021.1199 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormoor:v:47:y:2022:i:3:p:2065-2081

Access Statistics for this article

More articles in Mathematics of Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().