A FORBIDDEN MINOR CHARACTERIZATION AND RELIABILITY OF A CLASS OF PARTIAL 4-TREES

This paper characterizes a class G of partial 4-trees in terms of a se t of seven forbidden miners. The class G contains several known classe s of graphs, including both Delta - Y and Y - Delta graphs. A set of s ix graph reduction operations is defined, and it is shown that a graph G is an element of G iff G can be reduced to an edgeless graph by a f inite sequence of these operations. The all-terminal reliability R(G) of a graph G is the probability that G is connected. The characterizat ion of G is used to develop an O(n log n) algorithm to compute R(G) fo r all n-point graphs in G. The running time is O(n) for planar graphs in G. (C) 1995 John Wiley and Sons, Inc.