
Accession Number : ADA116276
Title : PolygontoChain 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 NPhard for general networks, although polynomialtime algorithms do exist for certain network configurations such as 'ladders' and 'wheels' and for some seriesparallel structures such as the wellknown 'twoterminal' seriesparallel networks. In this paper, we show that a class of seriesparallel networks, for which only exponentially complex algorithms were previously known, can be analyzed in polynomial time. In doing this, we introduce a new reliabilitypreserving graph reduction of general applicability and produce a lineartime algorithm for computing the reliability of any graph with an underlying seriesparallel 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