Survivable Network Design is the following problem: We are given two n × n matrices: a cost matrix dij and a (symmetric) connectivity requirement matrix rij

Subject:Computer SciencePrice:2.86 Bought3

Share With

Survivable Network Design is the following problem: We are given two n × n matrices: a cost matrix dij and a (symmetric) connectivity requirement matrix rij. We are also given a budget b. We want to find a undirected graph G = ({1, ..., n}, E) such that the total cost of all edges (i.e. ????(i,j)∈E dij) is at most b and there are exactly rij edge-disjoint paths between any two distinct vertices i and j, or if no such G exists, output "None". (A set of paths is edge-disjoint if no edge appears in more than one of them)

Show that Survivable Network Design is NP-Complete. (Hint: Reduce from a NP-Hard problem in Section 8 of the textbook. )