The search functionality is under construction.
The search functionality is under construction.

Graph Augmentation Problems with Degree-Unchangeable Vertices

Toshiya MASHIMA, Toshimasa WATANABE

  • Full Text Views

    0

  • Cite this

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.

Publication
IEICE TRANSACTIONS on Fundamentals Vol.E84-A No.3 pp.781-793
Publication Date
2001/03/01
Publicized
Online ISSN
DOI
Type of Manuscript
Special Section PAPER (Special Section of Selected Papers from the 13th Workshop on Circuits and Systems in Karuizawa)
Category

Authors

Keyword