Vertex Connectivity of Graphs: Algorithms and Bounds

Abstract

This report considers several problems concerning vertex connectivity of undirected graphs and presents new bounds and algorithms for these problems. Connectivity is one of the fundamental graph properties, and there has been a considerable amount of work on algorithms and structural aspects of this property. Applications of graph connectivity arise in operation research for scheduling problems, network analysis in electrical engineering, and many other real-life problems. The most direct application of this problem is for the reliability of networks. A fundamental criterion for evaluating performance of a communications network is its ability to withstand the failure of is not only real-life models but nonexistence of good upper bounds for the number of minimum size separating vertex sets of graphs. Another important measure of network reliability is to determine the subgraphs which are highly connected and to decompose the network into them. The results in all of these measures help in the design of optimum communication networks.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Aug 01, 1988
Accession Number
ADA199437

Entities

People

  • Arkady Kanevsky

Organizations

  • University of Illinois Urbana–Champaign

Tags

Communities of Interest

  • Energy and Power Technologies

DTIC Thesaurus Topics

  • Abstracts
  • Algorithms
  • Attachment
  • Classification
  • Computational Science
  • Computations
  • Computer Science
  • Decomposition
  • Electrical Engineering
  • Embedding
  • Illinois
  • Intervals
  • Networks
  • Numbers
  • Parallel Computing
  • Theses
  • Universities

Fields of Study

  • Computer science

Readers

  • Aerospace Test and Evaluation
  • Graph Algorithms and Convex Optimization.
  • Neural Network Machine Learning.