On minimum k-edge-connectivity augmentation for specified vertices of a graph with upper bounds on vertex-degree
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 subset of V and a function y : V --> Z(+) boolean OR {infinity}, find a smallest set E' of edges such that (V, E boolean OR E') has at least k edge-disjoint paths between any pair of vertices in S and such that, for any V E 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.
graphs augmentation problems degree constraints linear time algorithms edge-connectivity of a specified set of vertices