Carleton University
Technical Report TR-220
March 1993
On Multi-label Linear Interval Routing Schemes
Evangelos Kranakis, Danny Krizanc, S.S. Ravi
Abstract
We consider linear interval routing schemes studied in [3, 5] from a graph theoretic perspective. We examine how the number of linear intervals needed to obtain shortest path routings in networks is affected by the product and join operations on graphs. This approach allows us to generalize some of the results in [3, 5] concerning the minimum number of intervals needed to achieve shortest path routings in certain special classes of networks. We also establish the precise value of the minimum number of intervals needed to achieve shortest path routings in the network considered in [10].