Arc-Flags in Dynamic Graphs

Authors Emanuele Berrettini, Gianlorenzo D'Angelo, Daniel Delling



PDF
Thumbnail PDF

File

OASIcs.ATMOS.2009.2149.pdf
  • Filesize: 155 kB
  • 18 pages

Document Identifiers

Author Details

Emanuele Berrettini
Gianlorenzo D'Angelo
Daniel Delling

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

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)
    0
    PDF Downloads
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail