We introduce the (k,ℓ)-self-spanners graphs to model non-reliable interconnection networks. Such networks can be informally characterized as follows: if at most ℓ edges have failed, as long as two vertices remain connected, the distance between these vertices in the faulty graph is at most k times the distance in the non-faulty graph. By fixing the values k and ℓ (called stretch factor and fault-tolerance, respectively), we obtain specific new graph classes. We first provide characterizational, structural, and computational results for these classes. Then, we study relationships between the introduced classes and special graphs classes (distance-hereditary graphs, cographs, and chordal graphs), and common network topologies (grids, tori, hypercubes, butterflies, and cube-connected cycles) as well.

Self-spanner graphs

CICERONE, SERAFINO;DI STEFANO, GABRIELE;
2005

Abstract

We introduce the (k,ℓ)-self-spanners graphs to model non-reliable interconnection networks. Such networks can be informally characterized as follows: if at most ℓ edges have failed, as long as two vertices remain connected, the distance between these vertices in the faulty graph is at most k times the distance in the non-faulty graph. By fixing the values k and ℓ (called stretch factor and fault-tolerance, respectively), we obtain specific new graph classes. We first provide characterizational, structural, and computational results for these classes. Then, we study relationships between the introduced classes and special graphs classes (distance-hereditary graphs, cographs, and chordal graphs), and common network topologies (grids, tori, hypercubes, butterflies, and cube-connected cycles) as well.
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/4937
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 2
  • ???jsp.display-item.citation.isi??? 0
social impact