Shortest paths on dynamic graphs

DOI10.1111/J.1475-3995.2008.00649.XMaRDI QIDQ3638853zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

shortest pathsroad networkdynamic graph

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35)

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

Cites work

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

Cited in

(32)

• scientific article; zbMATH DE number 1808552 (Why is no real title available?)
• An all pairs shortest path algorithm for dynamic graphs
• Shortest Path Tree Computation in Dynamic Graphs
• scientific article; zbMATH DE number 7204496 (Why is no real title available?)
• A new dynamic graph structure for large-scale transportation networks
• scientific article; zbMATH DE number 1983277 (Why is no real title available?)
• Periodic paths on nonautonomous graphs
• Arc-flags in dynamic graphs
• Non-additive shortest path in the context of traffic assignment
• Fully dynamic update of arc-flags
• COMPUTING SHORTEST, FASTEST, AND FOREMOST JOURNEYS IN DYNAMIC NETWORKS
• Shortest-path algorithms and dynamic cost changes
• 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
• A universal concept for robust solving of shortest path problems in dynamically reconfigurable graphs
• Shortest-path queries in static networks
• 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

Describes a project that uses

Uses Software

• Algorithm 360
• LEDA

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)