Shortest paths on dynamic graphs

DOI10.1111/J.1475-3995.2008.00649.XzbMATH Open1188.90267OpenAlexW2166460706MaRDI QIDQ3638853FDOQ3638853

Authors: Giacomo Nannicini, Leo Liberti 

Publication date: 28 October 2009

Published in: International Transactions in Operational Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1111/j.1475-3995.2008.00649.x

Recommendations

• Algorithmic techniques for maintaining shortest routes in dynamic networks
• Shortest-path algorithms and dynamic cost changes
• On-line and dynamic algorithms for shortest path problems
• scientific article; zbMATH DE number 30302
• Dynamic shortest path problems with time-varying costs

zbMATH Keywords

shortest pathsroad networkdynamic graph

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35)

Cites Work

• Network flows. Theory, algorithms, and applications.
• A note on two problems in connexion with graphs
• An Appraisal of Some Shortest-Path Algorithms
• The shortest route through a network with time-dependent internodal transit times
• Shortest-path and minimum-delay algorithms in networks with time-dependent edge-length
• A new algorithm for reoptimizing shortest paths when the arc costs change
• Reoptimization procedures in shortest path problem
• Shortest paths in Euclidean graphs
• Speeding up dynamic shortest-path algorithms
• Dynamic shortest paths minimizing travel times and costs
• A generalized permanent label setting algorithm for the shortest path between specified nodes
• A Dual Shortest Path Algorithm
• Etude Et Extension D’Un Algorithme De Murghland
• Some New Techniques in Transportation Planning^†

Cited In (32)

• An all pairs shortest path algorithm for dynamic graphs
• Shortest Path Tree Computation in Dynamic Graphs
• Title not available (Why is that?)
• A new dynamic graph structure for large-scale transportation networks
• Title not available (Why is that?)
• Arc-flags in dynamic graphs
• Periodic paths on nonautonomous graphs
• COMPUTING SHORTEST, FASTEST, AND FOREMOST JOURNEYS IN DYNAMIC NETWORKS
• Fully dynamic update of arc-flags
• Shortest-path algorithms and dynamic cost changes
• Non-additive shortest path in the context of traffic assignment
• Algorithms – ESA 2004
• Parametric shortest-path algorithms via tropical geometry
• Shortest paths in reachability graphs
• Dynamic shortest path algorithm based on variable weight
• Systematic reviews as a metaknowledge tool: caveats and a review of available options
• Equilibrium distributions of discrete non-autonomous graphs
• Speeding up dynamic shortest-path algorithms
• Shortest-path queries in static networks
• A universal concept for robust solving of shortest path problems in dynamically reconfigurable graphs
• Cheapest paths in dynamic networks
• Dynamic shortest paths and transitive closure: algorithmic techniques and data structures
• Improvement of \(A^*\) algorithm and its application in shortest path problem in dynamic networks
• Disk-based shortest path discovery using distance index over large dynamic graphs
• Periodic dynamic graphs. Random walks problem and the shortest path
• Dynamic shortest paths containers
• Bidirectional \(A^*\) search on time-dependent road networks
• Optimization and sustainable development
• Algorithmic techniques for maintaining shortest routes in dynamic networks
• Dynamic multi-level overlay graphs for shortest paths
• GRASP. Extending graph separators for the single-source shortest-path problem
• Title not available (Why is that?)

Uses Software

• LEDA
• Algorithm 360

This page was built for publication: Shortest paths on dynamic graphs

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