We consider non-reliable networks characterized as follows: if some nodes have failed, as long as two nodes remain connected, the distance between any pair of such nodes in the faulty graph is at most k times the distance in the non- faulty graph. The smallest k that guarantees such property is called stretch factor of the network. In this work we review some known results about graphs that model networks with limited stretch factor and provide some new insights. In particular, we show that the split composition operation applied to minimal components like paths P3 and cycles C3 and C5 can be used to build networks with stretch factor less than two.

On Building Networks with Limited Stretch Factor

Cicerone, Serafino
2020-01-01

Abstract

We consider non-reliable networks characterized as follows: if some nodes have failed, as long as two nodes remain connected, the distance between any pair of such nodes in the faulty graph is at most k times the distance in the non- faulty graph. The smallest k that guarantees such property is called stretch factor of the network. In this work we review some known results about graphs that model networks with limited stretch factor and provide some new insights. In particular, we show that the split composition operation applied to minimal components like paths P3 and cycles C3 and C5 can be used to build networks with stretch factor less than two.
2020
978-3-030-44037-4
978-3-030-44038-1
File in questo prodotto:
File Dimensione Formato  
edasID_ciceronee_WAINA_2020.pdf

solo utenti autorizzati

Tipologia: Documento in Pre-print
Licenza: Dominio pubblico
Dimensione 136.3 kB
Formato Adobe PDF
136.3 kB Adobe PDF   Visualizza/Apri   Richiedi una copia
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/145326
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 1
  • ???jsp.display-item.citation.isi??? ND
social impact