A Set-Covering Approach for SONET Network Design

In this paper we formalize a graph-partitioning problem that arises in the design of SONET networks as a Set-Covering problem. We then improve the general performance ratio of the Greedy Algorithm proved by Chvátal for this particular case. \bigskip

Data and Resources

Additional Info

Field Value
Source https://hal.science/hal-00082799
Author Brauner, Nadia, Lemaire, Pierre
Maintainer CCSD
Last Updated May 10, 2026, 22:59 (UTC)
Created May 10, 2026, 22:59 (UTC)
Identifier hal-00082799
Language en
Rights https://about.hal.science/hal-authorisation-v1/
contributor Laboratoire Leibniz (Leibniz - IMAG) ; Université Joseph Fourier - Grenoble 1 (UJF)-Institut National Polytechnique de Grenoble (INPG)-Centre National de la Recherche Scientifique (CNRS)
creator Brauner, Nadia
date 2002-05-10T00:00:00
harvest_object_id 3874182f-8154-48f7-8c01-2cdd07be9563
harvest_source_id 3374d638-d20b-4672-ba96-a23232d55657
harvest_source_title test moissonnage SELUNE
metadata_modified 2025-09-27T00:00:00
set_spec type:UNDEFINED