Polygon-to-Chain Reductions and Network Reliability.
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.
Document Details
- Document Type
- Technical Report
- Publication Date
- Mar 01, 1982
- Accession Number
- ADA116276
Entities
People
- A. Satyanarayana
- R. Kevin Wood
Organizations
- University of California, Berkeley