On Minimum k-Edge-Connectivity Augmentation for Specified Vertices of a Graph with Upper Bounds on Vertex-Degree
Toshiya Mashima · IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences · 2006
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 ν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.