FINDING THE MOST VITAL EDGE WITH RESPECT TO K-TERMINAL RELIABILITY IN SERIES-PARALLEL NETWORKS

Abstract

Let K be contained in the vertex-set of a graph G. ''The most vital edge'' is the edge whose deletion yields the largest decrease in the K-terminal reliability, that is the probability that all vertices in K are connected. In this paper, we present a linear-time algorithm for finding the most vital edge with respect to K-terminal reliability in series-parallel networks.