Accession Number : ADA116276

Title :   Polygon-to-Chain Reductions and Network Reliability.

Descriptive Note : Research rept.,

Corporate Author : CALIFORNIA UNIV BERKELEY OPERATIONS RESEARCH CENTER

Personal Author(s) : Satyanarayana,A ; Wood,R Kevin

PDF Url : ADA116276

Report Date : Mar 1982

Pagination or Media Count : 34

Abstract : Analysis of network reliability is of major importance in computer, communication and power networks. Even the simplest models lead to computational problems which are NP-hard for general networks, although polynomial-time algorithms do exist for certain network configurations such as 'ladders' and 'wheels' and for some series-parallel structures such as the well-known 'two-terminal' series-parallel networks. In this paper, we show that a class of series-parallel networks, for which only exponentially complex algorithms were previously known, can be analyzed in polynomial time. In doing this, we introduce a new reliability-preserving graph reduction of general applicability and produce a linear-time algorithm for computing the reliability of any graph with an underlying series-parallel structure.

Descriptors :   *Networks, *Graphs, *Reliability, Mathematical models, Algorithms, Configurations, Polygons, Chains, Reliability, Polynomials, Reduction

Subject Categories : Electrical and Electronic Equipment
      Theoretical Mathematics
      Mfg & Industrial Eng & Control of Product Sys

Distribution Statement : APPROVED FOR PUBLIC RELEASE