Algebraic Aspects of Computing Network Reliability.

Abstract

The problem of calculating the two-terminal reliability of a network having edges that fail randomly and independently is known to be NP-hard, even in the case of directed acyclic networks. This paper discusses an iterative technique that provides at each iteration both upper and lower bounds on the exact reliability value. These bounds are shown to converge to the exact answer for the case of acyclic networks. Computational results indicate that for certain classes of graphs these bounds converge rapidly and provide excellent approximations to the true network reliability. (Author)

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Sep 01, 1986
Accession Number
ADA185501

Entities

People

  • D. R. Shier

Organizations

  • Clemson University

Tags

DTIC Thesaurus Topics

  • Abstracts
  • Air Force
  • Algorithms
  • Classification
  • Coefficients
  • Complex Systems
  • Computations
  • Exclusion Principle
  • Mathematical Analysis
  • Mathematics
  • Polynomials
  • Probability
  • Reliability
  • Scientific Research
  • Simulations
  • Terminals
  • Test And Evaluation

Readers

  • Graph Algorithms and Convex Optimization.
  • Operations Research
  • Statistical inference.