[30] In interval routing on a graph G = (V,E), V = {1,...,n}, each node i has for each incident edge e a (possibly empty) set of pairs of node labels representing disjoint intervals with wraparound. Each pair indicates the initial edge on a shortest path from i to any node in the interval, and for every node j = i there is such a pair. We are allowed to permute the labels of graph G to optimize the interval setting.

(a) Show that there are graphs such that for each interval routing scheme some incident edge on each of Ω(n) nodes are labeled by Ω(n) intervals.

(b) Show that for every d ≥ 3 there are graphs of maximal node degree d such that for each interval routing scheme some incident edge on each of Ω(n) nodes is labeled by Ω(n/ log n) intervals.

Comments. Source: [E. Kranakis and D. Krizanc, Proc. 13th Symp.

Theoret. Aspects Comput. Sci., Lect. Notes Comput. Sci., Vol. 1046, Springer-Verlag, 1996, pp. 529–540]. Item

(b) is improved by C. Gavoile and S. P´erenn`es [Proc. 15th ACM Symp. Principles Distr. Comput., 1996, pp. 125–133], who showed that for every interval routing scheme, each of Ω(n) edges is labeled by Ω(n) intervals. This shows that interval routing can be worse than straightforward coding of routing tables, which can be done in O(n2 log

d) bits total.