On Multi-Label Linear Interval Routing Schemes
E. Krankis · The Computer Journal · 1996
We consider linear interval routing schemes studied by [3,5] from a graph-theoretical perspective. We examine how the number of linear intervals needed to obtain shortest path routings in networks is affected by the product, join and composition operations on graphs. This approach allows us to generalize some of the results of [3,5] concerning the minimum number of intervals needed to achieve shortest path routings in certain special classes of networks. We also establish an Ω(n1/3) lower bound on the minimum number of intervals needed to achieve shortest path routings in the network considered.