1993/06/01 by Daniel Bienstock, Nicole Diaz, Nicole Romito Diaz
Computer Science · Engineering · #Interconnection Networks and Systems #VLSI and FPGA Design Techniques #Advanced Graph Theory Research
paper · doi:10.1137/0222034
Let G be a graph with weights on the edges, S a subset of vertices, and k an integer. The problem of computing a minimum-weight subset of edges that meets all the cuts of cardinality \leqslant k that separate pairs of vertices in S is considered. This problem is motivated by issues in network survivability. Assuming |S| = 2, it is shown that although this problem is NP-hard, it can be solved in linear time for each fixed value of k. Furthermore, if |S| > 2, the problem is NP-hard even for small values of k but can be solved in linear time for each fixed k and |S|.