Lower bounds on two-terminal network reliability (Q1116878)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Lower bounds on two-terminal network reliability |
scientific article |
Statements
Lower bounds on two-terminal network reliability (English)
0 references
1988
0 references
Computing the probability that two nodes in a probabilistic network are connected is a well-known computationally difficult problem. Two strategies are devised for obtaining lower bounds on the connection probability for two terminals. The first improves on the Kruskal-Katona bound by using efficient computations of small pathsets. The second strategy employs efficient algorithms for finding edge-disjoint paths. The resulting bounds are compared; while the edge-disjoint path bounds typically outperform the Kruskal-Katona bounds, they do not always do so. Finally, a method is outlined for developing a uniform bound which combines both strategies.
0 references
network reliability
0 references
two-terminal reliability
0 references
topological design
0 references
probabilistic network
0 references
lower bounds
0 references
connection probability
0 references
edge- disjoint paths
0 references
Kruskal-Katona bounds
0 references
0 references
0 references