Linear Algebra and Sequential Importance Sampling for Network Reliability

Abstract

The reliability polynomial of a graph gives the probability that a graph is connected as a function of the probability that each edge is connected. The coefficients of the reliability polynomial count the number of connected subgraphs of various sizes. Algorithms based on sequential importance sampling (SIS) have been proposed to estimate a graph's reliability polynomial. We develop a new bottom-up SIS algorithm for estimating the reliability polynomial by choosing a spanning tree and adding edges. This algorithm improves on existing bottom-up algorithms in that it has lower complexity O(E2) as opposed to O(EV3) and it uses importance sampling to reduce variance.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Dec 01, 2011
Accession Number
ADA558532

Entities

People

  • David G. Harris
  • Francis Sullivan
  • Isabel Beichl

Organizations

  • United States Department of Defense

Tags

DTIC Thesaurus Topics

  • Accuracy
  • Algebra
  • Algorithms
  • Applied Mathematics
  • Coefficients
  • Computational Complexity
  • Computer Science
  • Department Of Defense
  • Generators
  • Linear Algebra
  • Mathematics
  • New York
  • Polynomials
  • Probability
  • Reliability
  • Sampling
  • United States

Fields of Study

  • Engineering

Readers

  • Adaptive Control and Estimation with Uncertainty in Dynamic Systems.
  • Graph Algorithms and Convex Optimization.
  • Software Engineering