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.
Characterization results of all shortest paths interval routing schemes / M., Flammini; G., Gambosi; Nanni, Umberto; R. B., Tan. - In: NETWORKS. - ISSN 0028-3045. - STAMPA. - 37:4(2001), pp. 225-232. [10.1002/net.1017]
Characterization results of all shortest paths interval routing schemes
NANNI, Umberto;
2001
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.File | Dimensione | Formato | |
---|---|---|---|
VE_2001_11573-70303.pdf
solo gestori archivio
Tipologia:
Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza:
Tutti i diritti riservati (All rights reserved)
Dimensione
107.8 kB
Formato
Adobe PDF
|
107.8 kB | Adobe PDF | Contatta l'autore |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.