Efficient Algorithms for the Evaluation of Planar Network Reliability

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.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Mar 15, 1993
Accession Number
ADA263602

Entities

People

  • A. Satyanarayana
  • R. Tindell

Organizations

  • Stevens Institute of Technology

Tags

DTIC Thesaurus Topics

  • Algorithms
  • Applied Mathematics
  • Communication Systems
  • Computational Science
  • Computations
  • Computer Science
  • Computers
  • Electrical Engineering
  • Graph Theory
  • Mathematical Analysis
  • Mathematics
  • Probability
  • Scientists
  • Sequences
  • Standards
  • Terminals
  • Theoretical Computer Science

Readers

  • Neural Network Machine Learning.
  • Operations Research
  • Systems Analysis and Design