The k-edge-connectivity augmentation problem for a specified set of vertices of a graph with degree constraints, kECA-SV-DC, is defined as follows: "Given an undirected multigraph G = (V,E), a specified set of vertices S ⊆V and a function g: V → Z+ ∪{∞}, find a smallest set E' of edges such that (V,E ∪ E') has at least k edge-disjoint paths between any pair of vertices in S and such that, for any v ∈ V, E' includes at most g(v) edges incident to v, where Z+ is the set of nonnegative integers." This paper first shows polynomial time solvability of kECA-SV-DC and then gives a linear time algorithm for 2ECA-SV-DC.

The 2-vertex-connectivity augmentation problem of a graph with degree constraints, 2VCA-DC, is defined as follows: "Given an undirected graph G = (V,E) and an upper bound a(v;G) Z+{} on vertex-degree increase for each v V, find a smallest set E′ of edges such that (V,E E′) has at least two internally-disjoint paths between any pair of vertices in V and such that vertex-degree increase of each v V by the addition of E′ to G is at most a(v;G), where Z+ is the set of nonnegative integers." In this paper we show that checking the existence of a feasible solution and finding an optimum solution to 2VCA-DC can be done in O(|V|+|E|) time.

The 2-vertex-connectivity augmentation problem for a specified set of vertices of a graph with degree constraints, 2VCA-SV-DC, is defined as follows: "Given an undirected graph G = (V,E), a specified set of vertices S ⊆V with |S|3 and a function g:V→Z+∪{∞}, find a smallest set E' of edges such that (V,E ∪E') has at least two internally-disjoint paths between any pair of vertices in S and such that vertex-degree increase of each v ∈V by the addition of E' to G is at most g(v), where Z+ is the set of nonnegative integers." This paper shows a linear time algorithm for 2VCA-SV-DC.

The k-edge-connectivity augmentation problem with bipartition constraints (kECABP, for short) is defined by “Given an undirected graph G=(V, E) and a bipartition π = {VB, VW} of V with VB ∩ VW = ∅, find an edge set Ef of minimum cardinality, consisting of edges that connect VB and VW, such that G'=(V, E ∪ Ef) is k-edge-connected.” The problem has applications for security of statistical data stored in a cross tabulated table, and so on. In this paper we propose a fast algorithm for finding an optimal solution to (σ + 1)ECABP in O(|V||E| + |V2|log |V|) time when G is σ-edge-connected (σ > 0), and show that the problem can be solved in linear time if σ ∈ {1, 2}.

The k-vertex-connectivity augmentation problem for a specified set of vertices of a graph with degree-unchangeable vertices, kVCA(G,S,D), is defined as follows: "Given a positive integer k, an undirected graph G=(V,E), a specified set of vertices S V and a set of degree-changeable vertices D V, find a smallest set of edges E such that the vertex-connectivity of S in (V,E E) is at least k and E {(u,v) u,v D}. " The main result of the paper is that checking the existence of a solution and finding a solution to 2VCA(G,S,D) or 3VCA(G,S,D) can be done in O(|V|+|E|) or O(|V|(|V|+|E|)) time, respectively.

The (k + δ)-edge-connectivity augmentation problem for a specified set of vertices ((k + δ)ECA-SV) is defined as follows: "Given an undirected graph G =(V,E), a specified set of vertices Γ V, a subgraph G ′=(V,E ′) with λ(Γ;G ′) = k of G and a cost function c: E Z+ (nonnegative integers), find a set E* E - E ′of edges, each connecting distinct vertices of V, of minimum total cost such that λ(Γ;G″) k + δ for G"=(V,E ′∪E*)," where λ(Γ;G″) is the minimum value of the maximum number of edge disjoint paths between any pair of vertices in Γ of G". The paper proposes an O(Δ+|V||E|) time 2-approximation algorithm FSAR for (k + 1)ECA-SV with a restriction λ(V;G ′) = λ(Γ;G ′), where Δ is the time complexity of constructing a structural graph of a given graph G ′.

The k-edge-connectivity augmentation problem with multipartition constraints (kECAMP, for short) is defined by “Given a multigraph G=(V,E) and a multipartition π={V1,...,Vr} (r≥2) of V, that is, $V = igcup_{h = 1}^r V_h$ and Vi∩Vj=∅ (1≤i