In the first part of this thesis we generalise the well-known K-terminal reliability R(G,K) to different kinds of terminal vertices. By means of lattice theoretic tools, we propose a divide and conquer approach to compute this new reliability measure efficiently. The first part concludes with an improved path decomposition algorithm that computes R(G,K) much more memory and time efficient compared to current state-of-the-art algorithms. In the second part we discuss the counting of connected set partitions of a graph G and its application to network reliability problems. Again we utilise the lattice theoretic approach to carry out the counting efficiently. Finally, we investigate the domination reliability DR(G) of a graph G as an interesting network reliability measure.
| Identifer | oai:union.ndltd.org:DRESDEN/oai:qucosa:de:qucosa:26345 |
| Date | 01 November 2012 |
| Creators | Simon, Frank |
| Contributors | Tittmann, Peter, Baumann, Ulrike, Felsner, Stefan, Technische Universität Dresden |
| Source Sets | Hochschulschriftenserver (HSSS) der SLUB Dresden |
| Language | English |
| Detected Language | English |
| Type | doc-type:doctoralThesis, info:eu-repo/semantics/doctoralThesis, doc-type:Text |
| Rights | info:eu-repo/semantics/openAccess |
Page generated in 0.0018 seconds