Interval routing schemes |
| |
| Authors: | M Flammini G Gambosi S Salomone |
| |
| Affiliation: | (1) Dipartimento di Informatica e Sistemistica, University of Rome  La Sapienza, , via Salaria 113, I-00198 Rome, Italy;(2) Dipartimento di Matematica Pura ed Applicata, University of L'Aquila, via Vetoio loc. Coppito, I-67010 L'Aquila, Italy;(3) Dipartimento di Matematica, University of Rome Tor Vergata,, via della Ricerca Scientifica, I-00133 Rome, Italy;(4) Dipartimento di Matematica Pura ed Applicata, University of L'Aquila, via Vetoio loc. Coppito, I-67010 L'Aquila, Italy |
| |
| 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.This work was supported by the EEC ESPRIT II Basic Research Action Program under Contract No. 7141  Algorithms and Complexity II, by the EEC Human Capital and Mobility MAP project, and by the Italian MURST 40% project Algoritmi, Modelli di Calcolo e Strutture Informative. |
| |
| Keywords: | Distributed systems Compact routing tables Interval routing NP-completeness Shortest paths representation |
| 本文献已被 SpringerLink 等数据库收录！ |
|
