
For FullText 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.

BiConnectivity Augmentation for Specified Vertices of a Graph with Upper Bounds on VertexDegree Increase
Toshiya MASHIMA Takanori FUKUOKA Satoshi TAOKA Toshimasa WATANABE
Publication
IEICE TRANSACTIONS on Information and Systems
Vol.E89D
No.2
pp.751762 Publication Date: 2006/02/01
Online ISSN: 17451361 Print ISSN: 09168532 Type of Manuscript: Special Section PAPER (Special Section on Foundations of Computer Science) Category: Graph Algorithm Keyword: graphs , vertexconnectivity of a specified set of vertices , augmentation problems , degree constraints , linear time algorithms ,
Full Text: PDF(624.1KB) >>Buy this Article
Summary:
The 2vertexconnectivity augmentation problem for a specified set of vertices of a graph with degree constraints, 2VCASVDC, is defined as follows: "Given an undirected graph G = (V,E), a specified set of vertices S ⊆V with S3 and a function g:V→Z^{+}∪{∞}, find a smallest set E' of edges such that (V,E ∪E') has at least two internallydisjoint paths between any pair of vertices in S and such that vertexdegree 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 2VCASVDC.

