Distance oracles for time-dependent networks

DOI10.1007/s00453-015-0003-0zbMath1339.68055arXiv1309.4973OpenAlexW1489344685MaRDI QIDQ289929

Christos D. Zaroliagis, Spyros C. Kontogiannis

Publication date: 31 May 2016

Published in: Algorithmica, Automata, Languages, and Programming (Search for Journal in Brave)

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

zbMATH Keywords

distance oraclesFIFO propertytime-dependent shortest paths

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Data structures (68P05) Approximation algorithms (68W25)

Related Items (5)

Distance oracles for time-dependent networks ⋮ An Introduction to Temporal Graphs: An Algorithmic Perspective ⋮ Unnamed Item ⋮ An Introduction to Temporal Graphs: An Algorithmic Perspective^* ⋮ An axiomatic approach to time-dependent shortest path oracles

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
• 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
• The Space-Stretch-Time Tradeoff in Distance Oracles
• Preprocess, Set, Query!
• Shortest-path and minimum-delay algorithms in networks with time-dependent edge-length
• Approximate distance oracles
• Worst-case update times for fully-dynamic all-pairs shortest paths
• Time-Dependent Route Planning
• An Analysis of Stochastic Shortest Path Problems
• The time-dependent shortest pair of disjoint paths problem: Complexity, models, and algorithms
• Approximate Distance Oracles for Planar Graphs with Improved Query Time-Space Tradeoff
• 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
• Temporal Network Optimization Subject to Connectivity Constraints
• Distance Oracles beyond the Thorup--Zwick Bound
• Stochastic Shortest Paths Via Quasi-convex Maximization
• Algorithms – ESA 2004
• An Appraisal of Some Shortest-Path Algorithms
• Distance Oracles for Stretch Less Than 2
• Connectivity and inference problems for temporal networks
• A lower bound for the shortest path problem

This page was built for publication: Distance oracles for time-dependent networks