Series-Parallel Bounds for the Two-Terminal Reliability Problem
Published Online:1 Nov 1989https://doi.org/10.1287/ijoc.1.4.209
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.
