The Regenerator Location Problem
by Si Chen, Ivana Ljubic, S. Raghavan
In optical networks, the strength of an optical signal deteriorates as it gets farther from the source due to transmission
impairments in the fiber (attenuation, dispersion, cross-talk). In other words, the distance an optical signal may be sent
without losing or falsifying the information is limited. Therefore, it is necessary to regenerate the signals periodically
using regenerators. Given an optical network, the regenerator location problem searches for the subset of regenerators to be installed at minimum cost,
so that each pair of nodes can communicate with each other.
|Definition:|| Mathematically, the regenerator location problem (RLP) can be
described as follows. We are given:
|Complexity:|| The problem is NP-complete (see ). |
In case of uniform regenerator costs, the RLP is equivalent to the Maximum Leaf Spanning Tree Problem (MLSTP) (aka the Minimum Connected Dominating Set problem).
| Input graph G after preprocessing
(two nodes are connected iff the length of the
shortest path ≤dmax)
| A feasible RLP solution
|| Corresponding MLSTP solution
Graphs are provided after preprocessing, i.e., we proceed with the distance matrix D as follows: a node pair (u,v) is connected by an edge iff the length of the shortest path between u and v is ≤dmax. The nodes that are not connected by an edge are called not directly connected or NDC node pairs.