Accession Number : ADA263602


Title :   Efficient Algorithms for the Evaluation of Planar Network Reliability


Descriptive Note : Final rept.


Corporate Author : STEVENS INST OF TECH HOBOKEN NJ DEPT OF ELECTRICAL ENGINEERING AND COMPUTER SCIENCE


Personal Author(s) : Satyanarayana, A ; Tindell, R


Full Text : https://apps.dtic.mil/dtic/tr/fulltext/u2/a263602.pdf


Report Date : 15 Mar 1993


Pagination or Media Count : 22


Abstract : Computation of the all-terminal reliability for general classes of networks is NP-hard. The problem of characterizing subclasses of networks and designing efficient algorithms to compute their reliability is a major area of current research in network reliability. Supported by the ARO grant DAAL03-90-G-0078, we have made significant progress in enlarging the class of planar networks for which there exists efficient all-terminal reliability algorithms. The importance of this work is enhanced by the recent proof of Vertigan that the all-terminal network reliability problem for the full class of planar networks is NP-hard. A important outgrowth of our work is the discovery of general techniques for developing O(n log n) algorithms for a greatly enlarged class of planar and nonplanar networks.


Descriptors :   *ALGORITHMS , *COMPUTER NETWORKS , *RELIABILITY(ELECTRONICS) , COMPUTATIONS , TERMINALS , GRANTS , EFFICIENCY , RELIABILITY , NONPLANAR


Subject Categories : Electrical and Electronic Equipment
      Computer Systems


Distribution Statement : APPROVED FOR PUBLIC RELEASE