The Delta-Wye Approximation Procedure for Two-Terminal Reliability

Manoj K. Chari, Thomas A. Feo and J. Scott Provan
Additional contact information
Manoj K. Chari: Louisiana State University, Baton Rouge, Louisiana
Thomas A. Feo: University of Texas at Austin, Austin, Texas
J. Scott Provan: University of North Carolina, Chapel Hill, North Carolina

Operations Research, 1996, vol. 44, issue 5, 745-757

Abstract: The Delta-Wye Approximation Procedure (DWAP) is a procedure for estimating the two-terminal reliability of an undirected planar network G = ( V , E ) by reducing the network to a single edge via a sequence of local graph transformations. It combines the probability equations of Lehman—whose solutions provide bounds and approximations of two-terminal reliability for the individual transformations—with the Delta-Wye Reduction Algorithm of the second two authors—which performs the corresponding graph reduction in O (| V | 2 ) time. A computational study is made comparing the DWAP to one of the best currently known methods for approximating two-terminal reliability, and it is shown that the DWAP produces approximations that are between 10 and 80 times as accurate.

Keywords: reliability; (s; t)-connectedness reliability; analysis of algorithms network/graphs; application of the Delta-Wye reduction procedure for graphs (search for similar items in EconPapers)
Date: 1996
References: Add references at CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.44.5.745 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:44:y:1996:i:5:p:745-757

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().