A characterization of partial 3-trees with applications to network reliability

This thesis is concerned with a class of graphs called partial k-trees. A k-tree is defined recursively as follows: The complete graph K$\sb{\rm k}$ on k points is a k-tree. Given a k-tree G on n $\geq$ k points, a k-tree on n + 1 points is obtained by adding a new point u and edges connecting u to every point of a K$\sb{\rm k}$ in G. A graph is a partial k-tree if it is a subgraph of some k-tree. Our interest in k-trees and their subgraphs is motivated by some practical questions about the reliability of communication networks. For the reliability analysis, complex systems are often modelled as probabilistic networks. The edges of the network represent components or subsystems. Each of them fails with a given probability. The network reliability problem is to compute a measure of reliability given failure probabilities for the edges. One of the most general network reliability measures is the K-terminal reliability. Specifically, consider a probabilistic network G = (V, E) with the point set V and the edge set E. Let K be a specified subset of V with $\vert$K$\vert\geq$ 2. The K-terminal reliability R$\sb{\rm K}$(G) of G is the probability that the points in K are connected. An important special case of this problem is the all-terminal reliability where K is the entire point set of G. In the first part of the thesis, we establish some fundamental properties of partial 3-trees and show that a graph is a partial 3-tree if and only if it has no subgraph contractible to K$\sb5$, K$\sb{2,2,2}$, C$\sb8$(1,4), or K$\sb2$ x C$\sb5$. A graph G is said to be contractible to a graph H if H can be obtained from G by a sequence of edge contractions. Hither to, such a characterization of partial k-trees is known only for the values of k $\leq$ 2. The second part of the thesis is concerned with the all-terminal reliability analysis. This computation of all-terminal reliability of a network is known to be inherently difficult and, except for special cases, cannot be solved in time bounded by a polynomial in the size of the network. We present an efficient algorithm to compute the all-terminal reliability of partial 3-trees. The running time of this algorithm is O($\vert$V$\vert$) if G is planar partial 3-tree and is O($\vert$V$\vert\sp2$) for nonplanar partial 3-trees.