[22]

(a) Show that routing with any stretch factor > 1 in c log nrandom graphs can be done with n − 1 − (c + 3) log n nodes with local routing functions stored in at most log(n + 1) bits per node, and 1 +

(c + 3) log n nodes with local routing functions stored in 6n bits per node (hence the complete routing scheme is represented by fewer than

(6c + 20)n log n bits).

(b) Show that routing with stretch factor 2 in c log n-random graphs can be done using n − 1 nodes with local routing functions stored in at most log log n bits per node and 1 node with its local routing function stored in 6n bits (hence the complete routing scheme is represented by n log log n + 6n bits).

(c) Show that routing with stretch factor (c + 3) log n in c log n-random graphs can be done with local routing functions stored in O(1) bits per node (hence the complete routing scheme is represented by O(n) bits).

Comments. Hint: Use Lemma 6.4.5 on page 471 and restricted use of tables (Items

(a) and (b)) as in the proof of Theorem 6.5.1 and no tables in Item (c).