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

      0 references
      0 references
      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
      [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

      Identifiers

      0 references
      0 references
      0 references
      0 references