3-edge-connectivity augmentation problems
Takuo Watanabe, Tetsuya Narita, Akira Nakamura · 2003
The NP-completeness and an O(V/sup 3/) approximation algorithm are shown for the three-edge-connectivity augmentation problem: given a complete graph G=(V, E), a spanning subgraph G/sub 0/=(V, E'), and a cost function c of E into nonnegative integers, find E" contained in E-E' of minimum total cost such that the graph (V, E' union E") is simple and three-edge connected. It is proved that the problem is NP-complete, even if G/sub 0/ is two-vertex connected, and that the approximate solution obtained in this case has a total cost less than that of a certain spanning tree determined by G/sub 0/.>