Real life graphs and networks are prone to failure of nodes (vertices) and links (edges). In particular, for a pair of nodes s and t and a failing edge e in an n-vertex unweighted graph G = (V (G), E(G)), the replacement path p(s, t) is a shortest s- t path that avoids e. In this paper we present several efficient constructions that, for every (s, t) ? S ×T, where S, T ? V (G), and every e ? E(G), maintain the collection of all p(s, t), either implicitly (i.e., through compact data structures a.k.a. distance sensitivity oracles (DSO)), or explicitly (i.e., through sparse subgraphs a.k.a. fault-tolerant preservers (FTP)). More precisely, we provide the following results: (1) DSO: For every S, T ? V (G), we construct a DSO for maintaining S × T distances under single edge (or vertex) faults. This DSO has size O(n|S||T|) and query time of O(|S||T|). At the expense of having quasi-polynomial query time, the size of the oracle can be improved to O(n|S| + |T||S|n), which is optimal for |T| = (n|S|). When |T| = (n |S| ), the construction can be further refined in order to get a polynomial query time. We also consider the approximate additive setting, and show a family of DSOs that exhibits a tradeo between the additive stretch and the size of the oracle. Finally, for the meaningful single-source case, the above result is complemented by a lower bound conditioned on the Set-Intersection conjecture. This lower bound establishes a separation between the oracle and the subgraph settings. (2) FTP: We show the construction of a path-reporting DSO of size O(n/(|S||T|)/) reporting p(s, t) in O(|p(s, t)| + (n|S||T|)/) time. Such a DSO can be transformed into a FTP having the same size, and moreover it can be elaborated in order to make it optimal (up to a poly-logarithmic factor) both in space and query time for the special case in which T = V (G). Our FTP improves over previous constructions when |T| = O(|S|n) (up to inverse poly-logarithmic factors). (3) Routing and Labeling Schemes: For the well-studied single-source setting, we present a novel routing scheme, that allows to route messages on p(s,t) by using edge labels and routing tables of size O(n), and a header message of poly-logarithmic size. We also present a labeling scheme for the setting which is optimal in space up to constant factors.
Effcient oracles and routing schemes for replacement paths
Proietti Guido
2018
Abstract
Real life graphs and networks are prone to failure of nodes (vertices) and links (edges). In particular, for a pair of nodes s and t and a failing edge e in an n-vertex unweighted graph G = (V (G), E(G)), the replacement path p(s, t) is a shortest s- t path that avoids e. In this paper we present several efficient constructions that, for every (s, t) ? S ×T, where S, T ? V (G), and every e ? E(G), maintain the collection of all p(s, t), either implicitly (i.e., through compact data structures a.k.a. distance sensitivity oracles (DSO)), or explicitly (i.e., through sparse subgraphs a.k.a. fault-tolerant preservers (FTP)). More precisely, we provide the following results: (1) DSO: For every S, T ? V (G), we construct a DSO for maintaining S × T distances under single edge (or vertex) faults. This DSO has size O(n|S||T|) and query time of O(|S||T|). At the expense of having quasi-polynomial query time, the size of the oracle can be improved to O(n|S| + |T||S|n), which is optimal for |T| = (n|S|). When |T| = (n |S| ), the construction can be further refined in order to get a polynomial query time. We also consider the approximate additive setting, and show a family of DSOs that exhibits a tradeo between the additive stretch and the size of the oracle. Finally, for the meaningful single-source case, the above result is complemented by a lower bound conditioned on the Set-Intersection conjecture. This lower bound establishes a separation between the oracle and the subgraph settings. (2) FTP: We show the construction of a path-reporting DSO of size O(n/(|S||T|)/) reporting p(s, t) in O(|p(s, t)| + (n|S||T|)/) time. Such a DSO can be transformed into a FTP having the same size, and moreover it can be elaborated in order to make it optimal (up to a poly-logarithmic factor) both in space and query time for the special case in which T = V (G). Our FTP improves over previous constructions when |T| = O(|S|n) (up to inverse poly-logarithmic factors). (3) Routing and Labeling Schemes: For the well-studied single-source setting, we present a novel routing scheme, that allows to route messages on p(s,t) by using edge labels and routing tables of size O(n), and a header message of poly-logarithmic size. We also present a labeling scheme for the setting which is optimal in space up to constant factors.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.