A 2-Approximation Algorithm to (k + 1)-Edge-Connect a Specified Set of Vertices in a k-Edge-Connected Graph
Toshiya Mashima · IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences · 2005
The (k+δ)-edge-connectivity augmentation problem for a specified set of vertices ((k+δ)ECA-SV) is defined as follows: Given an undirected graph G' = (V, E), a specified set of vertices Γ ⊆ V, a subgraph G' = (V, E') with λ(Γ;G') = k of G and a cost function c: E → Z+ (nonnegative integers), find a set E* ⊆ E-E' of edges, each connecting distinct vertices of V, of minimum total cost such that λ(Γ;G″) ≥ k+δ for G″ = (V, E' ∪ E*), where λ(Γ;G″) is the minimum value of the maximum number of edge disjoint paths between any pair of vertices in Γ of G″. The paper proposes an O(Δ + |V||E|) time 2-approximation algorithm FSAR for (k + 1)ECA-SV with a restriction λ(V;G') = λ(Γ;G'), where Δ is the time complexity of constructing a structural graph of a given graph G'.