Searching among intervals and compact routing tables

Shortest paths in weighted directed graphs are considered within the context of compact routing tables. Strategies are given for organizing compact routing tables so that extracting a requested shortest path will takeo(k logn) time, wherek is the number of edges in the path andn is the number of vertices in the graph. The first strategy takesO (k+logn) time to extract a requested shortest path. A second strategy takes (k) time on average, assuming alln(n–1) shortest paths are equally likely to be requested. Both strategies introduce techniques for storing collections of disjoint intervals over the integers from 1 ton, so that identifying the interval within which a given integer falls can be performed quickly.This research was supported in part by the National Science Foundation under Grants CCR-9001241 and CCR-9322501 and by the Office of Naval Research under Contract N00014-86-K-0689.