An axiomatic approach to time-dependent shortest path oracles

DOI10.1007/s00453-021-00922-8zbMath1485.05044OpenAlexW4206942404MaRDI QIDQ2118212

Dorothea Wagner, Christos D. Zaroliagis, Spyros C. Kontogiannis

Publication date: 22 March 2022

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-021-00922-8

zbMATH Keywords

distance oraclesFIFO propertytime-dependent shortest paths

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85)

Uses Software

• Graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Distance oracles for time-dependent networks
• On the complexity of time-dependent shortest paths
• Time-dependent SHARC-routing
• Preserving order in a forest in less than logarithmic time and linear space
• Shortest paths in time-dependent FIFO networks
• The shortest route through a network with time-dependent internodal transit times
• Bidirectional A* search on time-dependent road networks
• Improved Approximation for Time-Dependent Shortest Paths
• Preprocess, Set, Query!
• Shortest-path and minimum-delay algorithms in networks with time-dependent edge-length
• Approximate distance oracles
• Time-Dependent Route Planning
• Design and implementation of an efficient priority queue
• Shortest route with time dependent length of edges and limited delay possibilities in nodes
• The time-dependent shortest pair of disjoint paths problem: Complexity, models, and algorithms
• Hierarchical Time-Dependent Oracles
• Algorithms for minimum-cost paths in time-dependent networks with waiting policies
• Distance Oracles for Sparse Graphs
• Shortest-path queries in static networks
• Minimum time-dependent travel times with contraction hierarchies
• Analysis and Experimental Evaluation of Time-Dependent Distance Oracles
• Engineering Oracles for Time-Dependent Road Networks
• An Appraisal of Some Shortest-Path Algorithms
• Distance Oracles for Stretch Less Than 2
• Approximate Distance Oracles with Improved Query Time

This page was built for publication: An axiomatic approach to time-dependent shortest path oracles