A 2-APPROXIMATION ALGORITHM FSA+1 TO (λ + 1)-EDGE-CONNECT A SPECIFIED SET OF VERTICES IN A λ-EDGE-CONNECTED GRAPH

摘要

The k-edge-connectivity augmentation problem for a specified set of vertices (kECA-SV) is defined as follows: "Given an undirected graph G = (V,E), a subgraph G′ = (V, E′) of G, a specified set of verticies Γ is contained in V and a cost function c: E → Z{sup}+ (non-negative integers), find a set E" is contained in E -