The 2-hop cover labeling of a graph is a data structure that recently received a lot of attention since it can be exploited to efficiently answer to shortest-path distance queries on large-scale networks.In this paper, we propose the first dynamic algorithm to update 2-hop cover labelings for distance queries under edge removals, and show that: (i) it is efficient in terms of the number of nodes that change their distance toward some other node of the network, as a consequence of an edge removal; (ii) it is able to preserve the minimality of the labeling, a desirable property that has impact on both size and query time.In addition, we combine the new method with the unique algorithm in the literature suitable to handle edge additions, thus obtaining the first fully dynamic algorithm for updating 2-hop cover labelings for distance queries.We also conduct an extensive experimental study on real and synthetic dynamic networks, to show the scalability and efficiency of our new methods.

Distance queries in large-scale fully dynamic complex networks

D'ANGELO, GIANLORENZO;D'EMIDIO, MATTIA;FRIGIONI, DANIELE
2016

Abstract

The 2-hop cover labeling of a graph is a data structure that recently received a lot of attention since it can be exploited to efficiently answer to shortest-path distance queries on large-scale networks.In this paper, we propose the first dynamic algorithm to update 2-hop cover labelings for distance queries under edge removals, and show that: (i) it is efficient in terms of the number of nodes that change their distance toward some other node of the network, as a consequence of an edge removal; (ii) it is able to preserve the minimality of the labeling, a desirable property that has impact on both size and query time.In addition, we combine the new method with the unique algorithm in the literature suitable to handle edge additions, thus obtaining the first fully dynamic algorithm for updating 2-hop cover labelings for distance queries.We also conduct an extensive experimental study on real and synthetic dynamic networks, to show the scalability and efficiency of our new methods.
9783319445427
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: http://hdl.handle.net/11697/103377
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 13
  • ???jsp.display-item.citation.isi??? 8
social impact