k, an undirected graph G=(V,E), a specified set of vertices S V and a set of degree-changeable vertices D V, find a smallest set of edges E such that the vertex-connectivity of S in (V,E E) is at least k and E {(u,v) u,v D}. " The main result of the paper is that checking the existence of a solution and finding a solution to 2VCA(G,S,D) or 3VCA(G,S,D) can be done in O(|V|+|E|) or O(|V|(|V|+|E|)) time, respectively." />


Graph Augmentation Problems with Degree-Unchangeable Vertices

Toshiya MASHIMA  Toshimasa WATANABE  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E84-A   No.3   pp.781-793
Publication Date: 2001/03/01
Online ISSN: 
DOI: 
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section of Selected Papers from the 13th Workshop on Circuits and Systems in Karuizawa)
Category: 
Keyword: 
graph,  connectivity augmentation,  vertex-connectivity,  degree-unchangeable vertices,  polynomial time algorithms,  

Full Text: PDF>>
Buy this Article




Summary: 
The k-vertex-connectivity augmentation problem for a specified set of vertices of a graph with degree-unchangeable vertices, kVCA(G,S,D), is defined as follows: "Given a positive integer k, an undirected graph G=(V,E), a specified set of vertices S V and a set of degree-changeable vertices D V, find a smallest set of edges E such that the vertex-connectivity of S in (V,E E) is at least k and E {(u,v) u,v D}. " The main result of the paper is that checking the existence of a solution and finding a solution to 2VCA(G,S,D) or 3VCA(G,S,D) can be done in O(|V|+|E|) or O(|V|(|V|+|E|)) time, respectively.