The Two-Edge Connectivity Survivable-Network Design Problem in Planar Graphs

摘要

Consider the following problem: given a graph with edge costs and a subset Q of vertices, find a minimum-cost subgraph in which there are two edge-disjoint paths connecting every pair of vertices in Q. The problem is a failure-resilient analog of the Steiner tree problem arising, for example, in telecommunications applications. We study a more generalmixed-connectivity formulation, also employed in telecommunications optimization. Given a number (or requirement) r(v) is an element of{0, 1, 2} for each vertex v in the graph, find a minimum-cost subgraph in which there are min{r(u), r(v)} edge-disjoint u-to-v paths for every pair u, v of vertices.