Accession Number : ADA182868
Title : An Efficient Way for Edge-Connectivity 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 edge-connectivity condition is called the vertex- or edge- connectivity augmentation problem. The unweighted version of some edge-connectivity 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 bridge-connectivity 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
Distribution Statement : APPROVED FOR PUBLIC RELEASE