Computer Science – Information Theory
Scientific paper
2011-05-30
Computer Science
Information Theory
9 pages, 2 figure
Scientific paper
In the field of computer science, the network reliability problem for evaluating the network failure probability has been extensively investigated. For a given undirected graph $G$, the network failure probability is the probability that edge failures (i.e., edge erasures) make $G$ unconnected. Edge failures are assumed to occur independently with the same probability. The main contributions of the present paper are the upper and lower bounds on the expected network failure probability. We herein assume a simple random graph ensemble that is closely related to the Erd\H{o}s-R\'{e}nyi random graph ensemble. These upper and lower bounds exhibit the typical behavior of the network failure probability. The proof is based on the fact that the cut-set space of $G$ is a linear space over $\Bbb F_2$ spanned by the incident matrix of $G$. The present study shows a close relationship between the ensemble analysis of the network failure probability and the ensemble analysis of the error detection probability of LDGM codes with column weight 2.
Wadayama Tadashi
Yano Akiyuki
No associations
LandOfFree
Probabilistic Analysis of the Network Reliability Problem on a Random Graph Ensemble does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Probabilistic Analysis of the Network Reliability Problem on a Random Graph Ensemble, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Probabilistic Analysis of the Network Reliability Problem on a Random Graph Ensemble will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-677904