logo
CanyamAI summaries for academic research
language
MobileMobile
  • Phone FeatureWeChat Mini Program
EnglishEnglish
noticeNotice
BlogBlog
delete
arrow
Return

Fishman's sampling plan for computing network reliability

delete2001-03-01
delete48
PRE
AI
E
E. Manzi *
M
Martine Labbé
G
Guy Latouche
DOI：10.1109/24.935016delete
deleteOriginal
deleteOriginal request for help
deleteShare
deleteSave
Abstract

Abstract

En 中文
This paper analyzes a sampling method proposed by Fishman [4] for computing the 2-terminal and global reliability of a network. It describes, completely and clearly, the sampling algorithm, and computation experiments on networks corresponding to a real situation as well as examples from the literature. A communication network is modeled by an undirected graph as a function of the set of vertices (the network nodes) and the set of edges (the links connecting pairs of vertices), Each edge is in 1 of 2 states (operational and failed), Failures are assumed to be statistically independent, A network is connected iff the set of edges that are operational, forms a spanning connected subgraph (a, subgraph containing at least 1 operational path between any 2 vertices), The problems of computing: 1) the 2-terminal network reliability (probability that between 2 given vertices there exists at least 1 operational path) and 2) the global network reliability (probability that the network is connected), are treated. For problem 1, Fishman [4] proposed a Monte Carlo sampling plan, which uses lower and upper bounds to increase its accuracy and efficiency, Although the ideas in [4] are useful, the paper lacks clarity, This paper provides i) a detailed, clear exposition of the Fishman method, ii) a complete description of the corresponding algorithm, iii) its extension for computing global reliability (problem 2), and iv) computational experiments on networks both new and in the literature. A Monte Carlo approach for these problems is fully justified by looking at their computational complexity. The exact computation of the network reliability (either 2-terminal or global) is a #P-complete problem (a problem harder than the whole hierarchy of NP-hard problems). If one looks for efficient algorithms, one must settle for approximations obtained by a heuristic procedure.
Keywords:
Monte Carlo sampling
network reliability
probabilistic algorithm

Journal

IEEE Transactions on Reliability cover
IEEE Transactions on Reliability
IF:
5.7
Papers:
2.7K
Citations:
8.5K

Organization

No organization information available