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):

Report Date:

1993-03-15

Pagination or Media Count:

22.0

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 On log n algorithms for a greatly enlarged class of planar and nonplanar networks.

Subject Categories:

  • Electrical and Electronic Equipment
  • Computer Systems

Distribution Statement:

APPROVED FOR PUBLIC RELEASE