We introduce new classes of graphs to investigate networks that guarantee constant delays even in the case of multiple edge failures. This means the following: as long as two vertices remain connected if some edges have failed, then the distance between these vertices in the faulty graph is at most a constant factor k times the original distance. In this extended abstract, we consider the case where the number of edge failures is bounded by a constant l. These graphs are called (k, l)–self-spanners. We prove that the problem of maximizing l for a given graph when k > 4 is fixed is NP-complete, whereas the dual problem of minimizing k when l is fixed is solvable in polynomial time. We show how the Cartesian product affects the self-spanner properties of the composed graph. As a consequence, several popular network topologies (like grids, tori, hypercubes, butterflies, and cube-connected cycles) are investigated with respect to their self-spanner properties.

Survivable Networks with Bounded Delay: The Edge Failure Case

CICERONE, SERAFINO;DI STEFANO, GABRIELE;
1999-01-01

Abstract

We introduce new classes of graphs to investigate networks that guarantee constant delays even in the case of multiple edge failures. This means the following: as long as two vertices remain connected if some edges have failed, then the distance between these vertices in the faulty graph is at most a constant factor k times the original distance. In this extended abstract, we consider the case where the number of edge failures is bounded by a constant l. These graphs are called (k, l)–self-spanners. We prove that the problem of maximizing l for a given graph when k > 4 is fixed is NP-complete, whereas the dual problem of minimizing k when l is fixed is solvable in polynomial time. We show how the Cartesian product affects the self-spanner properties of the composed graph. As a consequence, several popular network topologies (like grids, tori, hypercubes, butterflies, and cube-connected cycles) are investigated with respect to their self-spanner properties.
3-540-66916-7
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/11697/42122
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 5
  • ???jsp.display-item.citation.isi??? 1
social impact