Shortest paths on dynamic graphs |
| |
Authors: | Giacomo Nannicini Leo Liberti |
| |
Affiliation: | LIX, École Polytechnique, F-91128 Palaiseau, France E-mail:; Mediamobile, 10 rue d'Oradour sur Glane, 75015 Paris, France E-mail: , |
| |
Abstract: | Among the variants of the well-known shortest path problem, those that refer to dynamically changing graphs are theoretically interesting, as well as computationally challenging. Application-wise, there is an industrial need for computing point-to-point shortest paths on large-scale road networks whose arcs are weighted with a travelling time that depends on traffic conditions. We survey recent techniques for dynamic graph weights as well as dynamic graph topology. |
| |
Keywords: | shortest paths dynamic graph road network |
|
|