INTERVAL ROUTING SCHEMES

Authors
FLAMMINI M GAMBOSI G SALOMONE S
Citation
M. Flammini et al., INTERVAL ROUTING SCHEMES, Algorithmica, 16(6), 1996, pp. 549-568
Citations number
17
Categorie Soggetti
Computer Sciences",Mathematics,Mathematics,"Computer Science Software Graphycs Programming
Journal title
Algorithmica → ACNP
ISSN journal
01784617
Volume
16
Issue
6
Year of publication
1996
Pages
549 - 568
Database
ISI
SICI code
0178-4617(1996)16:6<549:IRS>2.0.ZU;2-R
Abstract
In this paper the problem of routing messages along shortest paths in a distributed network without using complete routing tables is conside red. In particular, the complexity of deriving minimum (in terms of nu mber of intervals) interval routing schemes is analyzed under differen t requirements. For all the cases considered NP-hardness proofs are gi ven, while some approximability results are provided. Moreover, relati ons among the different cases considered are studied.