Efficient Algorithms for the Evaluation of Planar Network Reliability
STEVENS INST OF TECH HOBOKEN NJ DEPT OF ELECTRICAL ENGINEERING AND COMPUTER SCIENCE
Pagination or Media Count:
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 On log n algorithms for a greatly enlarged class of planar and nonplanar networks.
- Electrical and Electronic Equipment
- Computer Systems