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.
summary: A special case of the IDP problem where all the edges have the same weight, is studied in @cite_1 . This special case is called the problem. Given a simple undirected graph @math and a value @math , we want to find a partitioning of @math , @math such that @math . The authors present two linear-time-approximation algorithms with fixed performance guarantee.