An efficient algorithm for constructing (σ+1)-edge-connected simple graphs by edge addition

摘要

The unweighted k-edge-connectivity augmentation problem (kECA for short) is defined as follows: "Given an undirected graph G = (V, E), find an edge set E' of minimum cardinality such that G' = (V, E∪E') is k-edge-connected." In this paper we consider (σ + 1)ECA under the following constraints: G is a σ-edge-connected simple graph and G' is also simple. It is known that this problem is NP-Hard in general and its difficulty depends on the number of leaves in a given graph. We propose an improved algorithm for finding a solution to the problem in the following sences: its time complexity is O(σ{sup}2|V|log(|V|/σ)+|E|) and it finds an optimum solution if |M|≥[σ/2]+α and a 3/2-approximate solution otherwise, for some nonnegative integer a and for a maximum matching M of the leaf-graph of G.