Recent developments in graph theory have shown the importance of the class of partial k-trees. This large class of graphs admits several algorithm design methodologies that render efficient solutions for a luge number of problems inherently difficult for general graphs. In this thesis we develop such algorithms to solve a variety of reliability problems on partial k-tree networks with node and edge failures. We also investigate the problem of designing uniformly optimal 2-trees with respect to the 2-terminal reliability measure.

We model a communication network as a graph in which nodes represent communication sites and edges represent bidirectional communica­tion lines. Each component (node or edge) has an associated probability of operation. Components of the network are in either operational or failed state and their failures are statistically independent. Under this model, the reliability of a network G is defined as the probability that a given connectivity condition holds. The I-terminal reliability of G, Rel₁(G), is the probability that any two of a given set of l nodes of G can commu­nicate. Robustness o( a network to withstand failures can be expressed through network resilience, Res(G), which is the expected number of distinct pairs of nodes that can communicate. Computing these and other similarly defined measures is #P-hard for general networks.

We use a dyumic programming paradigm to design linear time algorithms that compute Rel₁(G), Res(G), and some other reliability and resilience measures of a partial k-tree network given with an embedding in a k-tree (for a fixed k).

Reliability problems on directed networks are also inherently difficult. We present efficient algorithms for directed versions of typical reliability and resilience problems restricted to partial k-tree networks without node failures. Then we reduce to those reliability problems allowing both node and edge failures.

Finally, we study 2-terminal reliability aspects of 2-trees. We charac­terize uniformly optimal 2-trees, 2-paths, and 2-caterpillars with respect to Rel₂ and identify local graph operations that improve the 2-terminal reliability of 2-tree networks.