Reliability of Partial k-tree Networks
Loading...
Date
1990-06-08
Authors
Mata-Montero, Erick
Journal Title
Journal ISSN
Volume Title
Publisher
University of Oregon
Abstract
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 large
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 communication
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 l-terminal reliability of G, Rel1 ( G), is
the probability that any two of a given set of I nodes of G can communicate.
Robustness of 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 dynamic programming paradigm to design linear time algorithms that compute Rel1( 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 characterize
uniformly optimal 2-trees, 2-paths, and 2-caterpillars with respect
to Rel2 and identify local graph operations that improve the 2-terminal
reliability of 2-tree networks.
Description
133 pages
Keywords
2-trees, 2-terminal reliability measure, l-terminal reliability