Analysis and Optimization of Communication Networks with Flow Requirements

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 Summar