A 2-approximation algorithm FSA+1 to (λ+1)-edge-connect a specified set of vertices in a λ-edge-connected graph
Satoshi Taoka, Toshiya Mashima, Takuo Watanabe · 2003
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 /spl Gamma//spl sube/V and a cost function c: E/spl rarr/Z/sup +/ (non-negative integers), find a set E"/spl sube/E-E' of edges, each connecting distinct vertices of V, of minimum total cost such that /spl lambda/(/spl Gamma/; G'+E")/spl ges/k for G'+E"=(V, E'/spl cup/E")," where /spl lambda/(/spl Gamma/; G")/spl ges/k means that G" has at least k edge disjoint paths between any pair of vertices in /spl Gamma/. The paper proposes an O(/spl Delta/+|V/spl par/E|) time 2-approximate algorithm FSA+1 for (/spl lambda/+1)ECA-SV with /spl lambda/(V; G)=/spl lambda/(/spl Gamma/; G), where /spl lambda/=/spl lambda/(/spl Gamma/; G') and /spl Delta/ is the time complexity of constructing a structural graph of a given graph G'.