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.

Level thesis:degree_level

thesis.doctoral

Grantor dc:publisher

TU Bergakademie Freiberg

Year

2019

Author dc:creator

• Lange, Thomas

Contributors dc:contributor

• Schiermeyer, Ingo
• Tittmann, Peter

• graph theory
• network reliability
• connectivity
• probabilistic graphs
• Graphentheorie
• Netzwerkzuverlässigkeit
• Zusammenhangswahrscheinlichkeit