Parametric Shortest-Path Algorithms via Tropical Geometry

Michael Joswig
Michael Joswig
[email protected]
https://orcid.org/0000-0002-4974-9659
Chair of Discrete Mathematics/Geometry, Technische Universität Berlin, Berlin 10623, GermanyMax Planck Institute for Mathematics in the Sciences, Leipzig 04103, Germany
Search for more papers by this author
,
Benjamin Schröter
Benjamin Schröter
[email protected]
https://orcid.org/0000-0003-3153-5211
Department of Mathematics, KTH Royal Institute of Technology, Stockholm SE-100 44, Sweden
Search for more papers by this author

Chair of Discrete Mathematics/Geometry, Technische Universität Berlin, Berlin 10623, GermanyMax Planck Institute for Mathematics in the Sciences, Leipzig 04103, Germany

Search for more papers by this author

Benjamin Schröter

[email protected]

https://orcid.org/0000-0003-3153-5211

Department of Mathematics, KTH Royal Institute of Technology, Stockholm SE-100 44, Sweden

Search for more papers by this author

Published Online:17 Feb 2022https://doi.org/10.1287/moor.2021.1199

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.

cover image Mathematics of Operations Research

Volume 47, Issue 3

August 2022

Pages 1707-2545, C2

Article Information

Metrics

Information

Received:April 17, 2020
Accepted:June 30, 2021
Published Online:February 17, 2022

Cite as

Michael Joswig, Benjamin Schröter (2022) Parametric Shortest-Path Algorithms via Tropical Geometry. Mathematics of Operations Research 47(3):2065-2081.

https://doi.org/10.1287/moor.2021.1199

Keywords

PDF download

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Parametric Shortest-Path Algorithms via Tropical Geometry

Abstract

Volume 47, Issue 3

Article Information

Metrics

Information

Cite as

Keywords

Sign Up for INFORMS Publications Updates and News