The Bounded Cycle Cover Problem


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 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.

Download Information

Click on the following title to view and download the paper in PostScript format.

The Bounded Cycle Cover Problem (29 pages, 605 KB)
Dorit S. Hochbaum and Eli Olinick. To appear in INFORMS Journal on Computing.