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.