Heuristic methods for the "span elimination" problem in ring-based transport network design

An aspect that is common to much of the work on optimized design of multiple-ring SONET (or WDM) networks is that they treat the design as a form of graph-covering problem. This produces fully restorable designs but there may be unnecessary lower bounds on network cost when the ring set has strictly to protect every span in the fiber graph. "Span elimination" is the problem of finding those key spans of an existing fiber graph on which it is more effective not to route any demands, thereby avoiding the requirement for ring coverage on the span. Preliminary results, with two algorithms, show significant cost reductions in the designs that emerge from a coverage-based solver arising from judicious span elimination prior to the graph-covering process.