Minimum Cost ≤k Edges Connected Subgraph Problems

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.