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.
2001
all shortest paths; characterization; dynamic costs; interval routing; uniform costs
01 Pubblicazione su rivista::01a Articolo in rivista
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]
File allegati a questo prodotto
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.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11573/70303
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 5
  • ???jsp.display-item.citation.isi??? 4
social impact