Dynamic Arc-Flags in Road Networks

Gianlorenzo D'Angelo 1, 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 : In this work we introduce a new data structure, named Road-Signs, which allows us to efficiently update the Arc-Flags of a graph in a dynamic scenario. Road-Signs can be used to compute Arc-Flags, can be efficiently updated and do not require large space consumption for many real-world graphs like, e.g., graphs arising from road networks. In detail, we define an algorithm to preprocess Road-Signs and an algorithm to update them each time that a weight increase operation occurs on an edge of the network. We also experimentally analyze the proposed algorithms in real-world road networks showing that they yields a significant speed-up in the updating phase of Arc-Flags, at the cost of a very small space and time overhead in the preprocessing phase.
Type de document :
Communication dans un congrès
Panos M. Pardalos and Steffen Rebennack. 10th International Symposium, SEA 2011, May 2011, Kolimpari, Chania, Crete, Greece. Springer, 6630, pp.88-99, 2011, Lecture Notes in Computer Science; Experimental Algorithms. <10.1007/978-3-642-20662-7_8>
Liste complète des métadonnées


https://hal.inria.fr/hal-00644054
Contributeur : Gianlorenzo D'Angelo <>
Soumis le : mercredi 23 novembre 2011 - 14:57:06
Dernière modification le : mardi 22 mai 2012 - 16:26:48
Document(s) archivé(s) le : vendredi 24 février 2012 - 02:27:17

Fichier

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

Identifiants

Collections

Citation

Gianlorenzo D'Angelo, Daniele Frigioni, Camillo Vitale. Dynamic Arc-Flags in Road Networks. Panos M. Pardalos and Steffen Rebennack. 10th International Symposium, SEA 2011, May 2011, Kolimpari, Chania, Crete, Greece. Springer, 6630, pp.88-99, 2011, Lecture Notes in Computer Science; Experimental Algorithms. <10.1007/978-3-642-20662-7_8>. <hal-00644054>

Partager

Métriques

Consultations de
la notice

206

Téléchargements du document

538