THE COMPLEXITY OF INTERVAL ROUTING ON RANDOM GRAPHS

Several methods exist for routing messages in a network without using complete routing tables (compact routing). In k-interval routing schem es (k-IRS), links carry up to k intervals each. A message is routed ov er a certain link if its destination belongs to one of the intervals o f the link. We present some results for the necessary value of k in or der to achieve shortest-path routing. Even though low values of k suff ice for very structured networks, we show that for 'general graphs' in terval routing cannot significantly reduce the space requirements for shortest-path routing. In particular we show that for suitably large n , there are suitable values of p such that for randomly chosen graphs G E Q(n,p) the following holds, with high probability: if G admits an optimal k-IRS, then k=Omega(n(1-6/In(np)-1n(np)/In n)). The result is obtained by means of a novel matrix representation for the shortest pa ths in a network.