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." />


Bi-Connectivity Augmentation for Specified Vertices of a Graph with Upper Bounds on Vertex-Degree Increase

Toshiya MASHIMA   Takanori FUKUOKA   Satoshi TAOKA   Toshimasa WATANABE   

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E89-D   No.2   pp.751-762
Publication Date: 2006/02/01
Online ISSN: 1745-1361
Print ISSN: 0916-8532
Type of Manuscript: Special Section PAPER (Special Section on Foundations of Computer Science)
Category: Graph Algorithm
Keyword: 
graphs ,  vertex-connectivity of a specified set of vertices ,  augmentation problems ,  degree constraints ,  linear time algorithms ,  

Full Text: PDF(624.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 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.