Skip to Main content Skip to Navigation
Conference papers

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 , Laboratoire I3S - 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.
Document type :
Conference papers
Complete list of metadata

Cited literature [17 references]  Display  Hide  Download
Contributor : Gianlorenzo D'Angelo Connect in order to contact the contributor
Submitted on : Wednesday, November 23, 2011 - 2:57:06 PM
Last modification on : Saturday, June 25, 2022 - 11:06:56 PM
Long-term archiving on: : Friday, February 24, 2012 - 2:27:17 AM


Files produced by the author(s)




Gianlorenzo d'Angelo, Daniele Frigioni, Camillo Vitale. Dynamic Arc-Flags in Road Networks. 10th International Symposium, SEA 2011, May 2011, Kolimpari, Chania, Crete, Greece. pp.88-99, ⟨10.1007/978-3-642-20662-7_8⟩. ⟨hal-00644054⟩



Record views


Files downloads