An axiomatic approach to time-dependent shortest path oracles

DOI10.1007/S00453-021-00922-8zbMATH Open1485.05044OpenAlexW4206942404MaRDI QIDQ2118212FDOQ2118212

Dorothea Wagner, Christos Zaroliagis, Spyros 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

Recommendations

• Distance oracles for time-dependent networks
• Distance oracles for time-dependent networks
• Analysis and Experimental Evaluation of Time-Dependent Distance Oracles
• Hierarchical time-dependent oracles
• Core routing on dynamic time-dependent road networks

zbMATH Keywords

distance oraclesFIFO propertytime-dependent shortest paths

Mathematics Subject Classification ID

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

Cites Work

• Shortest-path queries in static networks
• Preserving order in a forest in less than logarithmic time and linear space
• Approximate distance oracles
• An Appraisal of Some Shortest-Path Algorithms
• 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
• Distance oracles for time-dependent networks
• Preprocess, Set, Query!
• Shortest-path and minimum-delay algorithms in networks with time-dependent edge-length
• Time-Dependent Route Planning
• The time-dependent shortest pair of disjoint paths problem: Complexity, models, and algorithms
• On the complexity of time-dependent shortest paths
• Algorithms for minimum-cost paths in time-dependent networks with waiting policies
• Distance Oracles for Sparse Graphs
• Minimum time-dependent travel times with contraction hierarchies
• Analysis and Experimental Evaluation of Time-Dependent Distance Oracles
• Time-dependent SHARC-routing
• Distance Oracles for Stretch Less Than 2
• Title not available (Why is that?)
• Design and implementation of an efficient priority queue
• Approximate Distance Oracles with Improved Query Time
• Hierarchical Time-Dependent Oracles
• Shortest route with time dependent length of edges and limited delay possibilities in nodes
• Title not available (Why is that?)
• Improved Approximation for Time-Dependent Shortest Paths
• Engineering Oracles for Time-Dependent Road Networks

Cited In (1)

• Title not available (Why is that?)

Uses Software

• Graphs

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2118212)