No label defined (Q3823399)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 4097115
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | No label defined |
scientific article; zbMATH DE number 4097115 |
Statements
1988
0 references
unreliable edges
0 references
directed graph
0 references
source
0 references
terminal vertex
0 references
s-t reliability
0 references
computer communication systems
0 references
sequence of matched lower and upper bounds
0 references
netwok reliability
0 references
0.8469579219818115
0 references
0.8464305996894836
0 references
0.8446579575538635
0 references
0.8428472876548767
0 references
0.8378827571868896
0 references
[For the entire collection see Zbl 0663.00003.] We consider here a directed graph \(G=(V,E)\) in which vertices are perfectly reliable but edges fail independently of one another. The reliability of edge k is denoted \(p_ k=1-q_ k\), where \(q_ k\) is the failure probabiity for the edge. The graph contains two distinguished vertices s and t, with s being the source and t being the terminal vertex. In this context, an important practical problem is that of calculating the s-t reliability \(R_{st}:\) namely, the probability that a message sent from vertex s reaches vertex t, using edges of an operating path. Such a problem arises, for example, in both transportation systems and computer communication systems when goods (or information) must be routed along a number of links, each subject to disruption or failure. Unfortunately, the calculation of \(R_{st}\) is known to be an NP-hard problem, even in the case when G is planar and acyclic.... An alternative, therefore, is to try to approximate network reliability. Various lower and upper bounds on \(R_{st}\) have been proposed, most recently the lower bound of \textit{D. R. Shier} [Graph theory with applications to algorithms and computer science, Proc. 5th Int. Conf., Kalamazoo/Mich. 1984, 741-752 (1985)] and the upper bounds of \textit{J. G. Shanthikumar} [Simple bounds for network reliability, Tech. Rep., School Business Administr., Univ. California (Berkeley 1984)] and \textit{A. W. Shogan} [IEEE Trans. Reliab. R-26 (1977), 322-327 (1978; Zbl 0373.90029)]. Our objective in this paper is to obtain a sequence of matched lower and upper bounds on netwok reliability: that is, a sequence of bounds \(LB_ i\), \(UB_ i\) on \(R_{st}\) that become progressively tighter with successive iterations.
0 references