On the Complexity of the Regenerator Placement Problem in Optical Networks

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 eve...

Full description

Saved in:
Bibliographic Details
Published in:IEEE/ACM transactions on networking 2011-04, Vol.19 (2), p.498-511
Main Authors: Flammini, M, Marchetti-Spaccamela, A, Monaco, G, Moscardelli, L, Zaks, S
Format: Article
Language:English
Subjects:
Algorithms
Approximation algorithms
Approximation methods
Complexity
Computational Complexity
Computer networks
Computer Science
Joining processes
Mathematical analysis
Optical communication
Optical fiber networks
optical networks
Placement
Polynomials
Regenerators
Repeaters
Routing
Routing (telecommunications)
Studies
wavelength division multiplexing (WDM)
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:1063-6692
1558-2566
DOI:10.1109/TNET.2010.2068309