The bounded cycle-cover problem

The bounded cycle-cover problem

0.00 Avg rating0 Votes
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: ,
Keywords: computational analysis
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 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.

Reviews

Required fields are marked *. Your email address will not be published.