Placement of regenerators in optical networks has attracted the attention of recent research works in optical networks. In this problem, we are given a network with an underlying topology of a graph G and with a set of requests that correspond to paths in G There is a need to put a regenerator every certain distance, because of a decrease in the power of the signal. In this paper, we investigate the problem of minimizing the number of locations to place the regenerators. We present analytical results regarding the complexity of this problem, in four cases, depending on whether or not there is a bound on the number of regenerators at each node, and depending on whether or not the routing is given or only the requests are given (and part of the solution is also to determine the actual routing). These results include polynomial time algorithms, NP-completeness results, approximation algorithms, and inapproximability results.

On the Complexity of the Regenerator Placement Problem in Optical Networks / Michele, Flammini; MARCHETTI SPACCAMELA, Alberto; Gianpiero, Monaco; Luca, Moscardelli; Shmuel, Zaks. - In: IEEE-ACM TRANSACTIONS ON NETWORKING. - ISSN 1063-6692. - STAMPA. - 19:2(2011), pp. 498-511. [10.1109/tnet.2010.2068309]

On the Complexity of the Regenerator Placement Problem in Optical Networks

MARCHETTI SPACCAMELA, Alberto;
2011

Abstract

Placement of regenerators in optical networks has attracted the attention of recent research works in optical networks. In this problem, we are given a network with an underlying topology of a graph G and with a set of requests that correspond to paths in G There is a need to put a regenerator every certain distance, because of a decrease in the power of the signal. In this paper, we investigate the problem of minimizing the number of locations to place the regenerators. We present analytical results regarding the complexity of this problem, in four cases, depending on whether or not there is a bound on the number of regenerators at each node, and depending on whether or not the routing is given or only the requests are given (and part of the solution is also to determine the actual routing). These results include polynomial time algorithms, NP-completeness results, approximation algorithms, and inapproximability results.
2011
approximation algorithms; complexity; optical networks; regenerators; wavelength division multiplexing (wdm)
01 Pubblicazione su rivista::01a Articolo in rivista
On the Complexity of the Regenerator Placement Problem in Optical Networks / Michele, Flammini; MARCHETTI SPACCAMELA, Alberto; Gianpiero, Monaco; Luca, Moscardelli; Shmuel, Zaks. - In: IEEE-ACM TRANSACTIONS ON NETWORKING. - ISSN 1063-6692. - STAMPA. - 19:2(2011), pp. 498-511. [10.1109/tnet.2010.2068309]
File allegati a questo prodotto
File Dimensione Formato  
VE_2011_11573-91178.pdf

solo gestori archivio

Tipologia: Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 1.01 MB
Formato Adobe PDF
1.01 MB 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/91178
 Attenzione

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

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 48
  • ???jsp.display-item.citation.isi??? 36
social impact