The Bounded Cycle-Cover Problem

INFORMS Journal on Computing · 2001 · Volume 13 · Issue 2

Abstract

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.

Keywords

Analysis of Algorithms, Networks-Graphs, Heuristics, Telecommunications

Enable JavaScript for citation tools and additional paper interactions.