In this paper we introduce the notions of blackout-tolerant temporal -spanner of a temporal graph G which is a subgraph of G that preserves the distances between pairs of vertices of interest in G up to a multiplicative factor of, even when the graph edges at a single time-instant become unavailable. In particular, we consider the single-source, single-pair, and all-pairs cases and, for each case we look at three quality requirements: exact distances (i.e.,), almost-exact distances (i.e., for an arbitrarily small constant), and connectivity (i.e., unbounded). For each combination we provide tight bounds, up to polylogarithmic factors, on the size, which is measured as the number of edges, of the corresponding blackout-tolerant-spanner for both general temporal graphs and for temporal cliques. Our result show that such spanners are either very sparse (i.e., they have edges) or they must have size in the worst case, where n is the number of vertices of G. To complete the picture, we also investigate the case of multiple blackouts.

Blackout-Tolerant Temporal Spanners

Bilo' D.;D'Angelo G.;Leucci S.;
2022-01-01

Abstract

In this paper we introduce the notions of blackout-tolerant temporal -spanner of a temporal graph G which is a subgraph of G that preserves the distances between pairs of vertices of interest in G up to a multiplicative factor of, even when the graph edges at a single time-instant become unavailable. In particular, we consider the single-source, single-pair, and all-pairs cases and, for each case we look at three quality requirements: exact distances (i.e.,), almost-exact distances (i.e., for an arbitrarily small constant), and connectivity (i.e., unbounded). For each combination we provide tight bounds, up to polylogarithmic factors, on the size, which is measured as the number of edges, of the corresponding blackout-tolerant-spanner for both general temporal graphs and for temporal cliques. Our result show that such spanners are either very sparse (i.e., they have edges) or they must have size in the worst case, where n is the number of vertices of G. To complete the picture, we also investigate the case of multiple blackouts.
2022
978-3-031-22049-4
978-3-031-22050-0
File in questo prodotto:
Non ci sono file associati a questo prodotto.
Pubblicazioni consigliate

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/200504
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 1
  • ???jsp.display-item.citation.isi??? 1
social impact