The bounded cycle-cover problem
We consider the bounded cycle-cover problem, which is to find a minimum cost cycle over 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 that find 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.
telecommunications heuristics analysis of algorithms networks-graphs