In this paper the problem of routing messages along shortest paths in a distributed network without using complete routing tables is considered. In particular, the complexity of deriving minimum (in terms of number of intervals) interval routing schemes is analyzed under different requirements. For all the cases considered NP-hardness proofs are given, while some approximability results are provided. Moreover, relations among the different cases considered are studied.

Flammini, M., Gambosi, G., Salomone, S. (1996). Interval routing schemes. ALGORITHMICA, 16(6), 549-568 [10.1007/BF01944351].

Interval routing schemes

GAMBOSI, GIORGIO;
1996-01-01

Abstract

In this paper the problem of routing messages along shortest paths in a distributed network without using complete routing tables is considered. In particular, the complexity of deriving minimum (in terms of number of intervals) interval routing schemes is analyzed under different requirements. For all the cases considered NP-hardness proofs are given, while some approximability results are provided. Moreover, relations among the different cases considered are studied.
1996
Pubblicato
Rilevanza internazionale
Articolo
Sì, ma tipo non specificato
Settore INF/01 - INFORMATICA
English
distributed systems; compact routing tables; interval routing; NP-completeness; shortest paths representation
Flammini, M., Gambosi, G., Salomone, S. (1996). Interval routing schemes. ALGORITHMICA, 16(6), 549-568 [10.1007/BF01944351].
Flammini, M; Gambosi, G; Salomone, S
Articolo su rivista
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/2108/43507
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 19
  • ???jsp.display-item.citation.isi??? ND
social impact