Characterization results of all shortest paths interval routing schemes

We give complete characterizations for the classes of graphs with uniform c ost links that admit optimum all shortest paths 1-SLIRS (strict linear inte rval routing schemes) and 1-LIRS (linear interval routing schemes). The cha racterization of all the interval routing schemes with uniform cost links t hat represent only a single shortest path is known to be NP-complete, For a ny integer k > 0, we also show that the class of graphs with dynamic cost l inks that admit optimum all shortest paths L-IRS (SIRS, LIRS, SLIRS) is equ ivalent to the class of graphs with dynamic cost links that admit an optimu m single shortest path l-IRS (SIRS, LIRS, SLIRS) and also equivalent to the class of graphs with dynamic cost links that admit single paths up to any constant stretch factor k-IRS (SIRS, LIRS, SLIRS). (C) 2001 John Wiley & So ns, Inc.