Distance oracles for time-dependent networks

DOI10.1007/978-3-662-43948-7_59zbMATH Open1339.68055arXiv1309.4973OpenAlexW1489344685MaRDI QIDQ289929FDOQ289929

Authors: Spyros Kontogiannis, Christos Zaroliagis 

Publication date: 31 May 2016

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

Abstract: We present the first approximate distance oracle for sparse directed networks with time-dependent arc-travel-times determined by continuous, piecewise linear, positive functions possessing the FIFO property. Our approach precomputes $(1+epsilon)-$approximate distance summaries from selected landmark vertices to all other vertices in the network. Our oracle uses subquadratic space and time preprocessing, and provides two sublinear-time query algorithms that deliver constant and $(1+sigma)-$approximate shortest-travel-times, respectively, for arbitrary origin-destination pairs in the network, for any constant $sigma>epsilon$. Our oracle is based only on the sparsity of the network, along with two quite natural assumptions about travel-time functions which allow the smooth transition towards asymmetric and time-dependent distance metrics.

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

Recommendations

• Distance oracles for time-dependent networks
• Distance Queries in Large-Scale Fully Dynamic Complex Networks
• Analysis and Experimental Evaluation of Time-Dependent Distance Oracles
• Betweenness in time dependent networks
• Distributed shortest-path protocols for time-dependent networks
• Time-dependent simple temporal networks: properties and algorithms
• DECOMPOSITION ALGORITHMS TO COMPUTE THE QUICKEST TIME DISTRIBUTION IN DYNAMIC NETWORKS
• Connectivity and inference problems for temporal networks
• Connectivity and inference problems for temporal networks

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)

Cites Work

• Shortest-path queries in static networks
• Approximate distance oracles
• Stochastic Shortest Paths Via Quasi-convex Maximization
• Temporal network optimization subject to connectivity constraints
• 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
• The Space-Stretch-Time Tradeoff in Distance Oracles
• Preprocess, set, query!
• Shortest-path and minimum-delay algorithms in networks with time-dependent edge-length
• Worst-case update times for fully-dynamic all-pairs shortest paths
• Time-dependent route planning
• Title not available (Why is that?)
• 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
• 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
• Distance Oracles beyond the Thorup--Zwick Bound
• Algorithms – ESA 2004
• Time-dependent SHARC-routing
• Distance Oracles for Stretch Less Than 2
• Title not available (Why is that?)
• Connectivity and inference problems for temporal networks
• A lower bound for the shortest path problem

Cited In (7)

• An axiomatic approach to time-dependent shortest path oracles
• Analysis and Experimental Evaluation of Time-Dependent Distance Oracles
• Distance oracles for time-dependent networks
• An Introduction to Temporal Graphs: An Algorithmic Perspective^*
• Distance Queries in Large-Scale Fully Dynamic Complex Networks
• Title not available (Why is that?)
• An Introduction to Temporal Graphs: An Algorithmic Perspective

Uses Software

• Graphs

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

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