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., G.G. (2001). Characterization results of all shortest paths interval routing schemes. NETWORKS, 37(4), 225-232.
Tipologia: | Articolo su rivista |
Citazione: | Flammini M., G.G. (2001). Characterization results of all shortest paths interval routing schemes. NETWORKS, 37(4), 225-232. |
Lingua: | English |
Settore Scientifico Disciplinare: | Settore INF/01 - Informatica |
Revisione (peer review): | Sì, ma tipo non specificato |
Tipo: | Articolo |
Rilevanza: | Rilevanza internazionale |
Digital Object Identifier (DOI): | http://dx.doi.org/10.1002/net.1017 |
Stato di pubblicazione: | Pubblicato |
Data di pubblicazione: | 2001 |
Titolo: | Characterization results of all shortest paths interval routing schemes |
Autori: | |
Autori: | Flammini M., Gambosi G., Nanni U., Tan R.B. |
Appare nelle tipologie: | 01 - Articolo su rivista |