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
      Operations Research

Distribution Statement : APPROVED FOR PUBLIC RELEASE