Reliability of Partial k-tree Networks
| dc.contributor.author | Mata-Montero, Erick | |
| dc.date.accessioned | 2023-06-20T20:41:20Z | |
| dc.date.available | 2023-06-20T20:41:20Z | |
| dc.date.issued | 1990-06-08 | |
| dc.description | 133 pages | en_US |
| dc.description.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. | en_US |
| dc.identifier.uri | https://hdl.handle.net/1794/28439 | |
| dc.language.iso | en | en_US |
| dc.publisher | University of Oregon | en_US |
| dc.rights | Creative Commons BY-NC-ND 4.0-US | en_US |
| dc.subject | 2-trees | en_US |
| dc.subject | 2-terminal reliability measure | en_US |
| dc.subject | l-terminal reliability | en_US |
| dc.title | Reliability of Partial k-tree Networks | en_US |
| dc.type | Article | en_US |