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
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
Distribution Statement : APPROVED FOR PUBLIC RELEASE