Premium
Characterization results of all shortest paths interval routing schemes
Author(s) -
Flammini M.,
Gambosi G.,
Nanni U.,
Tan R.B.
Publication year - 2001
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.1017
Subject(s) - shortest path problem , interval (graph theory) , routing (electronic design automation) , class (philosophy) , computer science , path (computing) , integer (computer science) , constrained shortest path first , mathematics , combinatorics , mathematical optimization , discrete mathematics , k shortest path routing , graph , computer network , artificial intelligence , programming language
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 ). © 2001 John Wiley & Sons, Inc.