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 and with a set of requests that correspond. to paths in . 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

Flammini M;
2011-01-01

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 and with a set of requests that correspond. to paths in . 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; optical networks - regenerators; wavelength division multiplexing (WDM)
File in questo prodotto:
File Dimensione Formato  
2013_IEEEACMTransNetw_19_Flammini.pdf

non disponibili

Tipologia: Versione Editoriale (PDF)
Licenza: Non pubblico
Dimensione 1.4 MB
Formato Adobe PDF
1.4 MB Adobe PDF   Visualizza/Apri   Richiedi una copia

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/20.500.12571/2749
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 48
  • ???jsp.display-item.citation.isi??? 36
social impact