Title :
3-edge-connectivity augmentation problems
Author :
Watanabe, Toshimasa ; Narita, Takanori ; Nakamura, Akira
Author_Institution :
Fac. of Eng., Hiroshima Univ., Japan
Abstract :
The NP-completeness and an O(V3) approximation algorithm are shown for the three-edge-connectivity augmentation problem: given a complete graph G=(V, E), a spanning subgraph G0=(V, E\´), and a cost function c of E into nonnegative integers, find E"⊆E-E\´ of minimum total cost such that the graph (V, E\´ ∪ E") is simple and three-edge connected. It is proved that the problem is NP-complete, even if G0 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 G0
Keywords :
approximation theory; computational complexity; directed graphs; trees (mathematics); NP-completeness; approximation algorithm; cost; cost function; minimum total cost; nonnegative integers; spanning subgraph; spanning tree; three-edge-connectivity augmentation problem; two-vertex connected; Approximation algorithms; Computational complexity; Cost function; Electrocardiography; Polynomials; Tin; Tree graphs;
Conference_Titel :
Circuits and Systems, 1989., IEEE International Symposium on
Conference_Location :
Portland, OR
DOI :
10.1109/ISCAS.1989.100359
