Two lower bounds for multi-label interval routing
Ssh Tse, Fcm Lau · 1997
Interval routing is a space-efficient method for point-to-point networks. The method has been incorporated in the design of a commercially available routing chip [7], and is a basic element in some compact routing methods (e.g., [4]). With up to one interval label per edge, the method has been shown to be nonoptimal for arbitrary graphs [9, 13], where optimality is measured in terms of the longest (routing) path in a graph. It is intuitive to think that the longest path would depend on the number of interval labels used. In this paper, using some non-planar graphs, we prove that even with a relatively large number of labels, interval routing still falls short of being optimal for arbitrary graphs. The bounds on the longest path we prove are 3 2 D, independent of any number of labels up to \\Theta(log n), where D is the diameter of the graph; and 5 4 D, independent of any number of labels from \\Theta(log n) to \\Theta( p n). Our lower bound results suggest that a large increase, a fac...