TITLE:The Compactness of Interval Routing
AUTHORS:Cyril Gavoille and David Peleg
ABSTRACT:
The compactness of a graph measures the space complexity of its
shortest path routing tables. Each outgoing edge of a node x is
assigned a (pairwise disjoint) set of addresses, such that the unique
outgoing edge containing the address of a node y is the first
edge of a shortest path from x to y. The complexity
measure used in the context of interval routing is the minimum number
of intervals of consecutive addresses needed to represent each such
set, minimized over all possible choices of addresses and all choices
of shortest paths. This paper establishes asymptotically tight bounds
of n/4 on the compactness of a n-node graph. More
specifically, it is shown that every n-node graph has
compactness at most n/4+o(n), and conversely, there
exists an n-node graph whose compactness is
n/4-o(n). Both bounds improve upon known results.