The SONET Edge-Partition Problem
by
Olivier Goldschmidt, Dorit S. Hochbaum, Asaf Levin, and Eli V. Olinick.

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 tex2html_wrap_inline131 -hard when tex2html_wrap_inline133 and present a linear-time tex2html_wrap_inline135 -approximation algorithm. For even k values we present an approximation scheme with a reduced ratio but with increased complexity.

  • Downloadable files:
    • olinick@engr.smu.edu