| The Complexity of Interval Routing on Random Graphs (1998) | |||||||||||||
Abstract | |||||||||||||
| Several methods exist for routing messages in a network without using complete routing tables (compact routing). In k-interval routing schemes (k-IRS), links carry up to k intervals each. A message is routed over a certain link if its destination belongs to one of the intervals of the link. We present some results for the necessary value of k in order to achieve shortest-path routing. Even though low values of k suffice for very structured networks, we show that for ‘general graphs’ interval 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 ∈ Gn, p the following holds, with high probability: if G admits an optimal k-IRS, then [equation: see PDF] . The result is obtained by means of a novel matrix representation for the shortest paths in a network. | |||||||||||||
Publication details | |||||||||||||
| |||||||||||||