OASIcs.ATMOS.2009.2149.pdf
- Filesize: 155 kB
- 18 pages
Document
Arc-Flags in Dynamic Graphs
Authors
-
Part of:
Volume:
9th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'09) (ATMOS 2009)
Series: Open Access Series in Informatics (OASIcs)
Conference: Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS) - License:
Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license
- Publication Date: 2009-11-25
Cite AsGet BibTex
Emanuele Berrettini, Gianlorenzo D'Angelo, and Daniel Delling. Arc-Flags in Dynamic Graphs. In 9th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'09). Open Access Series in Informatics (OASIcs), Volume 12, pp. 1-18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)
https://doi.org/10.4230/OASIcs.ATMOS.2009.2149
https://doi.org/10.4230/OASIcs.ATMOS.2009.2149
Abstract
Computation of quickest paths has undergoing a rapid development in recent
years. It turns out that many high-performance route planning algorithms are
made up of several basic ingredients. However, not all of those ingredients have
been analyzed in a \emph{dynamic} scenario where edge weights change after
preprocessing. In this work, we present how one of those ingredients, i.e.,
Arc-Flags can be applied in dynamic scenarios
Keywords
- Shortest Path
- Speed-Up Technique
- Dynamic Graph Algorithm Shortest Path
- Speed-Up Technique
- Dynamic Graph Algorithm
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads