A minimum 3-connectivity augmentation of a graph

摘要

The paper considers the minimum 3-connectivity augmentation problems: determining a minimum-weight set of edges to be added so as to 3-connect a given undirectted simple graph. The first result is that the problem is NP-complete even if a given graph and weights are restricted to a 2-connected graph and either 1 or 2, respectively. The second result is for the problem with all weights are equal: it is shown that the cardinality of a solution to the problem can be computed from a given graph and that there is an O(nv(nv+ne)2) algorithm for finding a solution, where nv and ne are the numbers of vertices and edges of a given graph, respectively.