Title :
A linear time algorithm for minimum augmentation to 3-connect specified vertices of a graph
Author :
Mashima, Toshiya ; Watanabe, Toshimasa
Author_Institution :
Dept. of Circuits & Syst., Hiroshima Univ., Japan
Abstract :
The subject of the paper is the 3-vertex-connectivity augmentation problem for a specified set of vertices (3VCA-SV), which is defined as follows: given an undirected graph G=(V, E) and a specified subset S of V with |S|>3, find a smallest set of edges to be added to G so that the resulting graph may have the property that, even after deleting any two vertices from it, there is a path between any pair of remaining vertices in S. The result of the paper is that 3VCA-SV can be solved optimally in linear time
Keywords :
computational complexity; graph theory; 3-connect specified vertices; 3-vertex-connectivity augmentation problem; 3VCA-SV; edge set; linear time algorithm; minimum augmentation; specified subset; undirected graph; Approximation algorithms; Circuits and systems; Ice; Polynomials; Systems engineering and theory;
Conference_Titel :
Circuits and Systems, 1997. ISCAS '97., Proceedings of 1997 IEEE International Symposium on
Print_ISBN :
0-7803-3583-X
DOI :
10.1109/ISCAS.1997.621905
