The Bounded Cycle Cover Problem
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.
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.
dorit@hochbaum.ieor.berkeley.edu
7/30/00