Abstract | ||
---|---|---|
An interval routing algorithm for general networks has been proposed separately by Santoro and Khatib and van Leeuwen and Tan. It works optimally for various regular networks, and for the non-regular case it never chooses a route longer than twice the diameter of the network. Van Leeuwen and Tan posed the fundamental question whether there is an optimal interval routing algorithm for any arbitrary network. In this paper we prove the lower-bound result that for certain networks the interval routing algorithm chooses a route which is half as long as the diameter of this network. This answers the question in a negative way. |
Year | DOI | Venue |
---|---|---|
1991 | 10.1093/comjnl/34.5.475 | Comput. J. |
Field | DocType | Volume |
Computer science,Path vector protocol,Destination-Sequenced Distance Vector routing,Theoretical computer science,Routing algorithm | Journal | 34 |
Issue | ISSN | Citations |
5 | 0010-4620 | 17 |
PageRank | References | Authors |
1.72 | 0 | 2 |
Name | Order | Citations | PageRank |
---|---|---|---|
P. Ružička | 1 | 47 | 2.92 |
Vusei-Ar | 2 | 17 | 1.72 |