Extensions to Polychain: Nonseparability Testing and Factoring Algorithm.
Abstract
PolyChain is a portable FORTRAN program for evaluating the reliability of a K-terminal network via polygon-to-chain reductions and the factoring algorithm. The first version of PolyChain allows the evaluation of the K-terminal reliability for series-parallel graphs. The algorithm implemented is a linear time algorithm introduced in 1982 by Satyanarayana and Wood. This report discusses the design and implementation of two features recommended in a previous document that enable PolyChain subroutines to treat a larger class of problems. The algorithm of Satyanarayana and Wood has a constraint on the topology of the input network, requiring it to be nonseparable. The original version of PolyChain does not test for this requirement. One of the features added to PolyChain discussed in this report is the implementation of a routine to check for this condition. The algorithm of Satyanarayana and Wood computes the reliability of a network with an underlying series-parallel structure. When the input network is not totally reducible an extension to the algorithm is required to obtain the reduced network. The second feature discussed in this report is the implementation of a factoring algorithm incorporated to PolyChain to insure the evaluation of the K-terminal network reliability for both series-parallel reducible and irreducible networks.
Document Details
- Document Type
- Technical Report
- Publication Date
- Dec 02, 1985
- Accession Number
- ADA164242
Entities
People
- Lucia I. P. Resende
Organizations
- University of California, Berkeley