Characterization results of all shortest paths interval routing schemes

We give complete characterizations for the classes of graphs with uniform cost links that admit optimum all shortest paths 1‐ SLIRS (strict linear interval routing schemes) and 1‐ LIRS (linear interval routing schemes). The characterization of all the interval routing schemes with uniform cost links that represent only a single shortest path is known to be NP‐complete. For any integer k > 0, we also show that the class of graphs with dynamic cost links that admit optimum all shortest paths k‐IRS ( SIRS, LIRS, SLIRS ) is equivalent to the class of graphs with dynamic cost links that admit an optimum single shortest path k‐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 ). © 2001 John Wiley & Sons, Inc.