Loading [MathJax]/extensions/MathZoom.js
A Set-Covering Approach for SONET Network Design
Brauner, Nadia ; Lemaire, Pierre
HAL, hal-00082799 / Harvested from HAL
Text on HAL
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
Publié le : 2002-07-05
Classification:  complexité,  recherche opérationnelle,  set-covering,  approximations,  telecommunication networks,  [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM],  [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO] 
@article{hal-00082799,
     author = {Brauner, Nadia and Lemaire, Pierre},
     title = {A Set-Covering Approach for SONET Network Design},
     journal = {HAL},
     volume = {2002},
     number = {0},
     year = {2002},
     language = {en},
     url = {http://dml.mathdoc.fr/item/hal-00082799}
}

Brauner, Nadia; Lemaire, Pierre. A Set-Covering Approach for SONET Network Design. HAL, Tome 2002 (2002) no. 0, . http://gdmltest.u-ga.fr/item/hal-00082799/