The Bounded Cycle-Cover Problem
The Bounded Cycle-Cover Problem
复制标题
DOI：
10.1287/ijoc.13.2.104.10516
复制
发表时间：
2001-03
期刊：
影响因子：
--
通讯作者：
D. Hochbaum;E. Olinick
中科院分区：
文献类型：
--
作者：
D. Hochbaum;E. Olinick
我们考虑有界循环覆盖问题，即寻找一个双连通图的最小代价循环覆盖，使得覆盖中的任何循环都不包含超过规定数量的边。这个问题出现在光纤通信网络的设计中，该网络采用多个自愈环为通信流量提供路由，即使在光纤切断或其他类型的链路故障的情况下也是如此。我们提出了这个问题，以及几个相关的问题，并开发了启发式算法，该算法基于这些相关问题的解决技术，为有界循环覆盖问题找到近最优解。这些算法的经验结果，应用于随机生成的问题实例，提出和讨论。
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.