"In this paper we focus on dynamic batch algorithms for single source shortest paths in graphs with positive real edge weights. A dynamic algorithm is called batch if it is able to handle graph changes that consist of multiple edge updates at a time, i.e. a batch. We propose a new algorithm to process a decremental batch (containing only delete and weight increase operations), a new algorithm to process an incremental batch (containing only insert and weight decrease operations), and a combination of these algorithms to process arbitrary sequences of incremental and decremental batches. These algorithms are update-sensitive, namely they are efficient w.r.t. to the number of nodes in the shortest paths tree that change the parent and\/or the distance from the source as a consequence of the changes."

Dynamically Maintaining Shortest Path Trees under Batches of Updates

D'EMIDIO, MATTIA;FRIGIONI, DANIELE;Leucci S;PROIETTI, GUIDO
2013-01-01

Abstract

"In this paper we focus on dynamic batch algorithms for single source shortest paths in graphs with positive real edge weights. A dynamic algorithm is called batch if it is able to handle graph changes that consist of multiple edge updates at a time, i.e. a batch. We propose a new algorithm to process a decremental batch (containing only delete and weight increase operations), a new algorithm to process an incremental batch (containing only insert and weight decrease operations), and a combination of these algorithms to process arbitrary sequences of incremental and decremental batches. These algorithms are update-sensitive, namely they are efficient w.r.t. to the number of nodes in the shortest paths tree that change the parent and\/or the distance from the source as a consequence of the changes."
978-3-319-03578-9
File in questo prodotto:
File Dimensione Formato  
c49.pdf

non disponibili

Licenza: Non specificato
Dimensione 240.77 kB
Formato Adobe PDF
240.77 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11697/89137
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 13
  • ???jsp.display-item.citation.isi??? ND
social impact