G = (V,E), a specified set of vertices SV and a function g: V → Z+ ∪{∞}, find a smallest set E' of edges such that (V,EE') has at least k edge-disjoint paths between any pair of vertices in S and such that, for any vV, 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." />


On Minimum k-Edge-Connectivity Augmentation for Specified Vertices of a Graph with Upper Bounds on Vertex-Degree

Toshiya MASHIMA  Satoshi TAOKA  Toshimasa WATANABE  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E89-A   No.4   pp.1042-1048
Publication Date: 2006/04/01
Online ISSN: 1745-1337
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Selected Papers from the 18th Workshop on Circuits and Systems in Karuizawa)
Category: 
Keyword: 
graphs,  edge-connectivity of a specified set of vertices,  augmentation problems,  degree constraints,  linear time algorithms,  

Full Text: PDF(324.6KB)
>>Buy this Article


Summary: 
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 SV and a function g: V → Z+ ∪{∞}, find a smallest set E' of edges such that (V,EE') has at least k edge-disjoint paths between any pair of vertices in S and such that, for any vV, 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.