Series-Parallel Bounds for the Two-Terminal Reliability Problem

Abstract

The two-terminal reliability problem for communication networks with unreliable links is a computationally difficult problem. Upper and lower bounds can be efficiently computed using graph-theoretical techniques based on edge-packing. We present a new technique for improving these bounds via approximation by series-parallel graphs. We also present some computational results for comparison with the known edge-packing bounds. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.