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

Full description

Saved in:
Bibliographic Details
Published in:Networks 2001-07, Vol.37 (4), p.225-232
Main Authors: Flammini, M., Gambosi, G., Nanni, U., Tan, R.B.
Format: Article
Language:English
Subjects:
all shortest paths
Applied sciences
characterization
dynamic costs
Exact sciences and technology
Flows in networks. Combinatorial problems
interval routing
Operational research and scientific management
Operational research. Management science
Telecommunications
Telecommunications and information theory
Teleprocessing networks. Isdn
uniform costs
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0028-3045
1097-0037
DOI:10.1002/net.1017