Fully Dynamic Maintenance of Arc-Flags in Road Networks

Gianlorenzo D'Angelo 1 Mattia D'Emidio 2 Daniele Frigioni 2 Camillo Vitale 2
1 MASCOTTE - Algorithms, simulation, combinatorics and optimization for telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Abstract : The problem of finding best routes in road networks can be solved by applying Dijkstra's shortest paths algorithm. Unfortunately, road networks deriving from real-world applications are huge yielding unsustainable times to compute shortest paths. For this reason, great research efforts have been done to accelerate Dijkstra's algorithm on road networks. These efforts have led to the development of a number of speed-up techniques, as for example Arc-Flags, whose aim is to compute additional data in a preprocessing phase in order to accelerate the shortest paths queries in an on-line phase. The main drawback of most of these techniques is that they do not work well in dynamic scenarios. In this paper we propose a new algorithm to update the Arc-Flags of a graph subject to edge weight decrease operations. To check the practical performances of the new algorithm we experimentally analyze it, along with a previously known algorithm for edge weight increase operations, on real-world road networks subject to fully dynamic sequences of operations. Our experiments show a significant speed-up in the updating phase of the Arc-Flags, at the cost of a small space and time overhead in the preprocessing phase.
Type de document :
Communication dans un congrès
11th International Symposium on Experimental Algorithms (SEA2012), Jun 2012, Bordeaux, France. Springer, 7276, pp.135-147, 2012, Lecture Notes in Computer Science. 〈10.1007/978-3-642-30850-5_13〉
Liste complète des métadonnées

Littérature citée [14 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00729008
Contributeur : Gianlorenzo D'Angelo <>
Soumis le : vendredi 7 septembre 2012 - 11:27:05
Dernière modification le : vendredi 7 septembre 2012 - 16:16:13
Document(s) archivé(s) le : samedi 8 décembre 2012 - 03:40:44

Fichier

main.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Gianlorenzo D'Angelo, Mattia D'Emidio, Daniele Frigioni, Camillo Vitale. Fully Dynamic Maintenance of Arc-Flags in Road Networks. 11th International Symposium on Experimental Algorithms (SEA2012), Jun 2012, Bordeaux, France. Springer, 7276, pp.135-147, 2012, Lecture Notes in Computer Science. 〈10.1007/978-3-642-30850-5_13〉. 〈hal-00729008〉

Partager

Métriques

Consultations de
la notice

178

Téléchargements du document

184