In a previous work, the authors introduced the class of "graphs with bounded induced distance of order k", (BID(k) for short) to model non-reliable interconnection networks. A network modeled as a graph in BID(k) can be characterized as follows: if some nodes have failed, as long as two nodes remain connected, the distance between these nodes in the faulty graph is at most k times the distance in the non-faulty graph. The smallest k such that G is in BID(k) is called "stretch number" of G. In this paper we give new characterization, algorithmic, and existence results about graphs with small stretch number.

Networks with Small Stretch Number

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

Abstract

In a previous work, the authors introduced the class of "graphs with bounded induced distance of order k", (BID(k) for short) to model non-reliable interconnection networks. A network modeled as a graph in BID(k) can be characterized as follows: if some nodes have failed, as long as two nodes remain connected, the distance between these nodes in the faulty graph is at most k times the distance in the non-faulty graph. The smallest k such that G is in BID(k) is called "stretch number" of G. In this paper we give new characterization, algorithmic, and existence results about graphs with small stretch number.
3-540-41183-6
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/37315
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 5
  • ???jsp.display-item.citation.isi??? ND
social impact