The 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:
Non ci sono file associati a questo prodotto.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.