An Efficient Way for Edge-Connectivity Augmentation.

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.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Apr 01, 1987
Accession Number
ADA182868

Entities

People

  • Toshimasa Watanabe

Organizations

  • University of Illinois Urbana–Champaign

Tags

DTIC Thesaurus Topics

  • Algorithms
  • Attachment
  • Classification
  • Computational Complexity
  • Computational Science
  • Computations
  • Computer Programming
  • Computer Programs
  • Computers
  • Engineering
  • Graph Theory
  • Illinois
  • Lists (Data Structures)
  • Security
  • Separators
  • Sequences
  • Trees (Data Structures)

Readers

  • Graph Algorithms and Convex Optimization.