IEEE Transactions on Communications · 2003 · 188 citations · 11 references
ComputingComputer ScienceAlgorithmsComputer NetworksOptimizationCombinatorial OptimizationInteger ProgrammingMesh NetworksNetwork OptimizationRoutingRouting AlgorithmsDisjoint PathsDisjoint Paths ProblemInteger Linear ProgrammingLinear Integer OptimizationNetwork Flow ProblemsOptical RoutingRouting In Mesh NetworksRouting Problems
We study the diverse routing problem in optical mesh networks. We use a general framework based on shared risk link groups to model the problem. We prove that the diverse routing problem is indeed NP-complete, a result that has been conjectured by several researchers previously. In fact, we show that even the fiber-span-disjoint paths problem, a special case of the diverse routing problem, is also NP-complete. We then develop an integer linear programming formulation and show through numerical results that it is a very viable method to solve the diverse routing problem for most optical networks found in many applications which typically have no more than a few hundred nodes and fiber spans.
11
Node-and edge-deletion NP-complete problems
Mihalis Yannakakis · 1978 · 444 citations · Full text
Computationally Related Problems
Sartaj Sahni · SIAM Journal on Computing · 1974 · 362 citations
Design protection for WDM optical networks
O. Crochat, J.-Y. Le Boudec · IEEE Journal on Selected Areas in Communications · 1998 · 150 citations · Full text
Computing, Computer Science, Design +17