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.

This publication has 0 references indexed in Scilit: