
Accession Number : ADA182868
Title : An Efficient Way for EdgeConnectivity Augmentation.
Descriptive Note : Technical rept.,
Corporate Author : ILLINOIS UNIV AT URBANA APPLIED COMPUTATION THEORY GROUP
Personal Author(s) : Watanabe,Toshimasa
PDF Url : ADA182868
Report Date : Apr 1987
Pagination or Media Count : 64
Abstract : The problem in which the object is to add a minimum weight set of edges to a graph G = (V,E) so as to satisfy a given vertex or edgeconnectivity condition is called the vertex or edge connectivity augmentation problem. The unweighted version of some edgeconnectivity augmentation problem for graphs without edges is shown to be polynomially solvable. Consider the following problems: (i) The strong connectivity augmentation problem for directed graphs. (ii) The bridgeconnectivity augmentation problem for undirected graphs. (iii) The biconnectivity augmentation problem for undirected graphs. An improvement is made to a previous algorithm. Keywords: Edge connectivity augmentation problem; Algorithm; Computational complexity.
Descriptors : *COMPUTATIONS, *GRAPHS, *NONLINEAR PROGRAMMING, ALGORITHMS, AUGMENTATION, EFFICIENCY, EDGES, WEIGHT
Subject Categories : Theoretical Mathematics
Operations Research
Distribution Statement : APPROVED FOR PUBLIC RELEASE