Parametric Shortest-Path Algorithms via Tropical Geometry

DOI10.1287/moor.2021.1199MaRDI QIDQ5868948

Michael Joswig, Benjamin Schröter

Publication date: 26 September 2022

Published in: Mathematics of Operations Research (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1904.01082

zbMATH Keywords

tropical geometry; Dijkstra's algorithm; traffic networks; parameterized shortest paths

Mathematics Subject Classification ID

90C35: Programming involving graphs or networks

90C31: Sensitivity, stability, parametric optimization

68R10: Graph theory (including graph drawing) in computer science

90B06: Transportation, logistics and supply chain management

90B20: Traffic problems in operations research

05C12: Distance in graphs

14T90: Applications of tropical geometry

90C24: Tropical optimization (e.g., max-plus optimization)

Uses Software

• polymake
• GitHub