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 L-IRS (SIRS, LIRS, SLIRS) is equivalent to the class of graphs with dynamic cost links that admit an optimum 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 & Sons, Inc.

Flammini, M., Gambosi, G., Nanni, U., Tan, R.b. (2001). Characterization results of all shortest paths interval routing schemes. NETWORKS, 37(4), 225-232 [10.1002/net.1017].

Characterization results of all shortest paths interval routing schemes

GAMBOSI, GIORGIO;
2001-01-01

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 L-IRS (SIRS, LIRS, SLIRS) is equivalent to the class of graphs with dynamic cost links that admit an optimum 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 & Sons, Inc.
2001
Pubblicato
Rilevanza internazionale
Articolo
Sì, ma tipo non specificato
Settore INF/01 - INFORMATICA
English
All shortest paths; Characterization; Dynamic costs; Interval routing; Uniform costs
Flammini, M., Gambosi, G., Nanni, U., Tan, R.b. (2001). Characterization results of all shortest paths interval routing schemes. NETWORKS, 37(4), 225-232 [10.1002/net.1017].
Flammini, M; Gambosi, G; Nanni, U; Tan, Rb
Articolo su rivista
File in questo prodotto:
Non ci sono file associati a questo prodotto.

Questo articolo è pubblicato sotto una Licenza Licenza Creative Commons Creative Commons

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/2108/52904
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? 4
social impact