DIMACS TR: 93-23
Consecutive Cuts and Paths, and Bounds on k-Terminal Reliability
Authors: Heidi J. Strayer and Charles J. Colbourn
Shanthikumar developed an upper bound for
two--terminal reliability based on consecutive s-t cutsets.
Subsequently, Shier generalized this strategy to obtain upper bounds from
cutsets, and lower bounds from pathsets, when the cutsets or pathsets form
a semilattice structure.
We examine a restricted case of Shier's method that yields a k-terminal lower
bound based on consecutive pathsets.
Our approach employs a common reduction of consecutive cut and path bounds to
the computation of the two--terminal reliability of an interval graph
with imperfect vertices.
Computational results are given to support the observation that the
consecutive paths lower bound is competitive with the best efficiently
computable bounds that are currently available.
We then apply the consecutive path bound to reduce, in some cases
dramatically, the number of states generated in a most probable state
Paper available at:
DIMACS Home Page