text: This paper presents a new method and a constraint-based objective function to solve two problemsrelated to the design of optical telecommunication networks, namely the Synchronous Optical Net-work Ring Assignment Problem (SRAP) and the Intra-ring Synchronous Optical Network DesignProblem (IDP). These network topology problems can be represented as a graph partitioning withcapacity constraints as shown in previous works. We present here a new objective function and anew local search algorithm to solve these problems. Experiments conducted in C
  @cite_1: Motivated by a problem arising in the design of telecommunications networks using the SONET standard, we consider the problem of covering all edges of a graph using subgraphs that contain at most k edges with the objective of minimizing the total number of vertices in the subgraphs. We show that the problem is -hard when k ≥ 3 and present a linear-time -approximation algorithm. For even k values, we present an approximation scheme with a reduced ratio but with increased complexity. © 2002 Wiley Periodicals, Inc.
  @cite_4: We consider the problem of interconnecting a set of customer sites using bidirectional SONET rings of equal capacity. Each site is assigned to exactly one ring and a special ring, called the federal ring, interconnects the other rings together. The objective is to minimize the total cost of the network subject to a ring capacity limit where the capacity of a ring is determined by the total bandwidth required between sites assigned to the same ring plus the total bandwidth request between these sites and sites assigned to other rings.We present exact, integer-programming based solution techniques and fast heuristic algorithms for this problem. We compare the results from applying the heuristic algorithms with those produced by the exact methods for real-world as well as randomly generated problem instances. We show that two of the heuristics find solutions that cost at most twice that of an optimal solution. Empirical evidence indicates that in practice the algorithms perform much better than their theoretical bound and often find optimal solutions.
summary: These two problems have been well studied. It has been proven that they are both @math -hard ( @cite_4 , @cite_1 ).