A Linear Time Algorithm for Bi-Connectivity Augmentation of Graphs with Upper Bounds on Vertex-Degree Increase
Takanori Fukuoka · IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences · 2005
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.