Hardness of robust network design
Authors:
Abstract
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. © 2007 Wiley Periodicals, Inc. NETWORKS, Vol. 50(1), 50–54 2007Keywords
This publication has 18 references indexed in Scilit:
- Provisioning virtual private networks under traffic uncertaintyNetworks, 2006
- Routing of Uncertain Traffic DemandsOptimization and Engineering, 2005
- Virtual Private Network Design: A Proof of the Tree Routing Conjecture on Ring NetworksLecture Notes in Computer Science, 2005
- New Approaches for Virtual Private Network DesignLecture Notes in Computer Science, 2005
- Optimal oblivious routing in polynomial timeJournal of Computer and System Sciences, 2004
- Making intra-domain routing robust to changing and uncertain traffic demands2003
- Networks new economical virtual privateCommunications of the ACM, 2003
- Multicommodity max-flow min-cut theorems and their use in designing approximation algorithmsJournal of the ACM, 1999
- Designing Least-Cost Nonblocking Broadband NetworksJournal of Algorithms, 1997
- Some simplified NP-complete graph problemsTheoretical Computer Science, 1976