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
Mfg & Industrial Eng & Control of Product Sys
Distribution Statement : APPROVED FOR PUBLIC RELEASE