Consider routing schemes for n-node graphs G = (V,E), V =

{1,...,n}, with maximal node degree

d. Choose the most convenient labeling to facilitate compact routing schemes.

(a) Show that for every d ≥ 3 there are networks for which any shortestpath routing scheme requires a total of Ω(n2/ log n) bits.

(b) The same as Item

(a) but now with stretch factor < 2 requiring a total of Ω(n2/ log2 n) bits.

Comments. Source: [E. Kranakis and D. Krizanc, Ibid.]. Item

(a) is improved by C. Gavoile and S. P´erenn`es [Ibid.] for 3 ≤ d ≤ n (0 << 1)

to Θ(n2 log d). This is optimal, since straightforward coding of routing tables takes O(n2 log

d) bits total.