ISSN:
1432-0541
Keywords:
Distributed systems
;
Compact routing tables
;
Interval routing
;
NP-completeness
;
Shortest paths representation
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
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.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01944351
Permalink