A Survey of Network Reliability.

Abstract

We present a brief survey of the current state of the art in network reliability. We survey only exact methods; Monte Carlo methods are not surveyed. Most network reliability problems are, in the worst case, NP-hard and are, in a sense, more difficult than many standard combinatorial optimization problems. Although the above sounds very discouraging, there are in fact linear and polynomial time algorithms for network reliability problems of special structure. We review general methods for network reliability computation and discuss the central role played by domination theory in network reliability computational complexity. We also point out the connection with the more general problem of computing the reliability of coherent structure. The class of coherent structures contains both directed and undirected networks as well as logic (or fault) tress without not gates.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jul 01, 1983
Accession Number
ADA133545

Entities

People

  • Avinash Agrawal
  • Richard E. Barlow

Organizations

  • University of California, Berkeley

Tags

DTIC Thesaurus Topics

  • Air Force
  • Algorithms
  • California
  • Communication Networks
  • Computational Complexity
  • Computations
  • Computer Communications
  • Computer Networks
  • Computer Science
  • Engineering
  • Monte Carlo Method
  • Networks
  • Operations Research
  • Polynomials
  • Surveys
  • Topology
  • United States

Readers

  • Adaptive Control and Estimation with Uncertainty in Dynamic Systems.
  • Instructional Design and Training Evaluation.
  • Neural Network Machine Learning.