Minimum cost ? k edges connected subgraph problems

Abstract

The minimum-cost network design problem is considered in the case where an optimum network remains connected, after deleting any ≤ k edges which form a matching in the optimum network. For the case k=1, we develop heuristic algorithms to compute a lower and an upper bounds for optimal value of objective function. These algorithms are used in the branch and bound methods to find a solution to the considered problem. We also present computational results. © 2010 Elsevier B.V.