Characterization results of all shortest paths interval routing schemes

Characterization results of all shortest paths interval routing schemes

0.00 Avg rating0 Votes
Article ID: iaor20023720
Country: United States
Volume: 37
Issue: 4
Start Page Number: 225
End Page Number: 232
Publication Date: Jun 2001
Journal: Networks
Authors: , , ,
Abstract:

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).

Reviews

Required fields are marked *. Your email address will not be published.