Article ID: | iaor20021950 |
Country: | United States |
Volume: | 13 |
Issue: | 2 |
Start Page Number: | 104 |
End Page Number: | 119 |
Publication Date: | Mar 2001 |
Journal: | INFORMS Journal On Computing |
Authors: | Hochbaum Dorit S., Olinick Eli V. |
Keywords: | computational analysis |
We consider the bounded cycle-cover problem, which is to find a minimum cost cycle cover of a two-connected graph such that no cycle in the cover contains more than a prescribed numbered of edges. This problem arises in the design of fiber-optic telecommunications networks that employ multiple self-healing rings to provide routing for communication traffic, even in the event of a fiber cut or other type of link failure. We present this problem, along with several related problems, and develop heuristic algorithms and near optimal solutions for the bounded cycle-cover problem based on solution techniques for these related problems. Empirical results of these algorithms, applied to randomly generated problem instances, are presented and discussed.