Premium
Consecutive cuts and paths, and bounds on k ‐terminal reliability
Author(s) -
Strayer Heidi J.,
Colbourn Charles J.
Publication year - 1995
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230250309
Subject(s) - upper and lower bounds , bounding overwatch , mathematics , terminal (telecommunication) , combinatorics , reliability (semiconductor) , path (computing) , interval (graph theory) , discrete mathematics , computer science , mathematical analysis , physics , quantum mechanics , artificial intelligence , telecommunications , power (physics) , programming language
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 bounding method.