Computing shortest distances is a central task in many graph applications. Since it is impractical to recompute shortest distances from scratch every time the graph changes, many algorithms have been proposed to incrementally maintain shortest distances after edge deletions or insertions. In this paper, we address the problem of maintaining all-pairs shortest distances in dynamic graphs and propose novel efficient incremental algorithms, working both in main memory and on disk. We prove their correctness and provide complexity analyses. Experimental results on real-world datasets show that current main-memory algorithms become soon impractical, disk-based ones are needed for larger graphs, and our approach significantly outperforms state-of-the-art algorithms.

Efficient Maintenance of All-Pairs Shortest Distances

GRECO, Sergio;MOLINARO, Cristian;
2016-01-01

Abstract

Computing shortest distances is a central task in many graph applications. Since it is impractical to recompute shortest distances from scratch every time the graph changes, many algorithms have been proposed to incrementally maintain shortest distances after edge deletions or insertions. In this paper, we address the problem of maintaining all-pairs shortest distances in dynamic graphs and propose novel efficient incremental algorithms, working both in main memory and on disk. We prove their correctness and provide complexity analyses. Experimental results on real-world datasets show that current main-memory algorithms become soon impractical, disk-based ones are needed for larger graphs, and our approach significantly outperforms state-of-the-art algorithms.
2016
978-1-4503-4215-5
File in questo prodotto:
Non ci sono file associati a questo prodotto.

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/20.500.11770/171045
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 3
  • ???jsp.display-item.citation.isi??? ND
social impact