CINECA IRIS Institutional Research Information System
IRIS è la soluzione IT che facilita la raccolta e la gestione dei dati relativi alle attività e ai prodotti della ricerca. Fornisce a ricercatori, amministratori e valutatori gli strumenti per monitorare i risultati della ricerca, aumentarne la visibilità e allocare in modo efficace le risorse disponibili.
EnglishThe authors settle the complexity status of the robust network design problem in undirected graphs. The fact that the flow-cut gap in general graphs can be large, poses some difficulty in establishing a hardness result. Instead, the authors introduce a single-source version of the problem where the flow-cut gap is known to be one. They then show that this restricted problem is coNP-Hard. This version also captures, as special cases, the fractional relaxations of several problems including the spanning tree problem, the Steiner tree problem, and the shortest path problem.
| Autori interni: | |
| Autori: | C. CHEKURI; G.P. ORIOLO; SCUTELLA' M; F.B. SHEPHERD |
| Titolo: | Hardness of Robust Network Design |
| Anno del prodotto: | 2007 |
| Digital Object Identifier (DOI): | 10.1002/net.20165 |
| Appare nelle tipologie: | 1.1 Articolo in rivista |
File in questo prodotto:
http://hdl.handle.net/11568/114423
Copyright © 2021