The SONET edge‐partition problem

Abstract

Abstract 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.