M.Sc Thesis

M.Sc StudentHartstein Itamar
SubjectOn the Complexity of the Regenerator Location
Problem - Treewidth and Other Parameters
DepartmentDepartment of Computer Science
Supervisors PROFESSOR EMERITUS Shmuel Zaks
PROF. Mordohay Salom
Full Thesis textFull thesis text - English Version


In this thesis we deal with the Regenerator Location Problem in optical networks. One of the main problems in optical network design is the loss of signal energy after light travels large distances. Optical amplifiers are used to amplify the signal, but unfortunately they also introduce noise. Therefore, at some point, the signal must be regenerated so it will remain above a certain SNR (Signal-to-Noise Ratio) threshold. Regenerators are placed after every fixed distance d in order to enable communication over large distances .

We model an optical network as an undirected graph G = (V, E), and a set Q of communication requests between pairs of terminals in V. We investigate two variations of the regenerator location problem: one in which we are given a routing P of the requests in Q, and one in which we are required to find also the routing. In both cases, each path in P must contain at least one regenerator in every d consecutive internal vertices. Our goal for both problems is to minimize the number of regenerator locations used by the solution, that is, the number of vertices containing at least one regenerator .

Both variations of the problem are NP-Hard in the general case, and existing works have attempted to overcome this problem in various ways, including heuristics, simulations, approximation algorithms and identification of polynomial-time cases. In this work, we investigate the parameterized complexity of the problem. That is, we investigate the inherent difficulty of the problems at hand with respect to multiple parameters of the input. Our results include fixed parameter tractability results, polynomial algorithms for fixed parameter values, and several NP-Hardness results .

Several parameters are considered in this work. The main parameter discussed is the treewidth of the input graph. Informally, the treewidth is a measure of the similarity of a graph to a tree. Another parameter discussed here is the vertex load of the path set when the routing is given - that is, the maximum number of paths in which any vertex serves as an intermediate node. Other parameters discussed are the distance between consecutive regenerators, d, and the number of connection requests .