An Optimal Lower Bound for Interval Routing in General Networks
Savio S. H. Tse, Francis C. M. Lau · 1997
. Interval routing is a space-efficient (compact) routing method for point-to-point communication networks. It has already been shown that it is impossible to find labelings that would lead to all-shortest-paths for arbitrary graphs. In this paper, we prove the lower bound of 2D \\Gamma 3 on the longest routing path for arbitrary graphs, where D = O( p n) is the graph's diameter and n is the number of nodes, as well as a lower bound of 2D \\Gamma o(D) for D = O(n). Our results are very close to the best known upper bound which is 2D. 1 Introduction Interval routing was first proposed by Santoro and Khatib [2], and subsequently refined by van Leeuwen and Tan [6]. The idea is to label the nodes by integers (called node numbers) from a cyclicly ordered set, say, f0; 1; : : : ; n \\Gamma 1g, where n is the number of nodes and the edges by intervals of the form hp; qi, where p; q are node numbers. hp; qi is the set fp; p + 1; : : : ; qg if p ! q, or fp; p + 1; : : : ; n \\Gamma 1; 0; : : :...