In this thesis, we will study the concept of k-edge connected and k-connected reliability.
There, vertices are modelled as fail-safe and edges fail stochastically independent. For a fixxed k, the network is then considered operational when each pair of vertices has k edge disjoint or internally disjoint paths, respectively, connecting them in the surviving subnetwork. Thus, the property of being operating covers the connectivity of the surviving graph together with some minimum bandwidth.
We study essential and irrelevant edges for those reliability measures. Further, we study a splitting approach to transform the reliability of the graph into the probability that subgraphs have a certain connectivity. We also extend an approximation algorithm of Karger from the All-Terminal Unreliability to k-edge connected Unreliability and study the k-edge connected Reliability for some special graph classes, namely graphs with restricted treewidth, edge-transitive graphs and the complete graph.:1 Introduction
2 Monotone Systems
2.1 Monotone Binary Systems
2.2 Monotone Multistate Systems
3 Graphs and Graph Operations
4 Higher Connectivity
4.1 Connectivity Number and Edge-Connectivity Number
4.2 Algorithms
5 Essential and Irrelevant Edges
6 Probabilistic Graphs and Reliability Measures
7 Reductions
8 Splitting
8.1 Some Special Cases for Small Separators/Cuts
8.2 Generalization to Arbitrary Separators
8.3 Constructing the Splitting Classes for 2-ec, 3-ec and 2-vc
8.4 Minimality
8.5 A Lattice-based Approach
9 An Approximation Scheme
9.1 Definition of Approximation Algorithms
9.2 The FPRAS for All-Terminal-Unreliability
9.3 Improved Bound for the Number of alpha-cuts
9.4 Extension to k-edge-connected Unreliability
10 Special Graph Classes
10.1 Graphs with Bounded Treewidth
10.2 Edge-Transitive Graphs
10.3 The Complete Graph
11 Future Research
12 Summary
| Identifer | oai:union.ndltd.org:DRESDEN/oai:qucosa:de:qucosa:33755 |
| Date | 24 April 2019 |
| Creators | Lange, Thomas |
| Contributors | Schiermeyer, Ingo, Tittmann, Peter, TU Bergakademie Freiberg |
| Source Sets | Hochschulschriftenserver (HSSS) der SLUB Dresden |
| Language | English |
| Detected Language | English |
| Type | info:eu-repo/semantics/publishedVersion, doc-type:doctoralThesis, info:eu-repo/semantics/doctoralThesis, doc-type:Text |
| Rights | info:eu-repo/semantics/openAccess |
Page generated in 0.0021 seconds