G = (V,E), a specified set of vertices SV with |S|3 and a function g:VZ+∪{∞}, find a smallest set E' of edges such that (V,EE') has at least two internally-disjoint paths between any pair of vertices in S and such that vertex-degree increase of each vV 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." />
 For Full-Text PDF, please login, if you are a member of IEICE, or go to Pay Per View on menu list, if you are a nonmember of IEICE.
 Bi-Connectivity Augmentation for Specified Vertices of a Graph with Upper Bounds on Vertex-Degree IncreaseToshiya MASHIMA  Takanori FUKUOKA  Satoshi TAOKA  Toshimasa WATANABE  Publication IEICE TRANSACTIONS on Information and Systems   Vol.E89-D   No.2   pp.751-762Publication Date: 2006/02/01 Online ISSN: 1745-1361Print ISSN: 0916-8532Type of Manuscript: Special Section PAPER (Special Section on Foundations of Computer Science)Category: Graph AlgorithmKeyword: graphs,  vertex-connectivity of a specified set of vertices,  augmentation problems,  degree constraints,  linear time algorithms,  Full Text: PDF(622.1KB)>>Buy this Article Summary:  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.