The Regenerator Location Problem
by Si Chen, Ivana Ljubic, S. Raghavan 
Intro: 
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, crosstalk). 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 NPcomplete (see [1]). 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 
BENCHMARK INSTANCES 

Data Format: 
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.

Bibliography: 

Contact:  ivana.ljubic @univie.ac.at 