Shortest paths in time-dependent FIFO networks

DOI10.1007/s00453-010-9461-6zbMath1241.68088WikidataQ62037435 ScholiaQ62037435MaRDI QIDQ2428679

Masoud T. Omran, Frank Dehne, Jörg-Rüdiger Sack

Publication date: 26 April 2012

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-010-9461-6

zbMATH Keywords

algorithms; shortest paths; FIFO property; time-dependent networks; earliest arrival time

Mathematics Subject Classification ID

68W05: Nonnumerical algorithms

68M10: Network design and communication in computer systems

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

Related Items

Distance oracles for time-dependent networks, On the complexity of time-dependent shortest paths, Determining time-dependent minimum cost paths under several objectives, Optimising waiting at nodes in time-dependent networks: cost functions and applications, An axiomatic approach to time-dependent shortest path oracles, On computing Pareto optimal paths in weighted time-dependent networks

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A note on two problems in connexion with graphs
• Time depending shortest-path problems with applications to railway networks
• The overlay of lower envelopes and its applications
• Shortest paths in a network with time-dependent flow speeds
• The shortest route through a network with time-dependent internodal transit times
• Undirected single-source shortest paths with positive integer weights in linear time
• Shortest-path and minimum-delay algorithms in networks with time-dependent edge-length
• Minimum weight paths in time-dependent networks
• A simple and fast label correcting algorithm for shortest paths
• Minimum Time and Minimum Cost-Path Problems in Street Networks with Periodic Traffic Lights
• Faster shortest-path algorithms for planar graphs