University of Twente Student Theses
Probabilistic analysis of highly connected random geometric graphs
Reijnders, V.M.J.J. (2016) Probabilistic analysis of highly connected random geometric graphs.
|
PDF
786kB |
| Abstract: | In this thesis we investigate how to obtain cheap reliable networks, and how the problem of finding them behaves. We study reliability in terms of k-edge-connectivity and k-vertex connectivity in graphs. In these graphs, we either charge per edge or we assign power to vertices and charge per vertex. When charging per vertex, the network can be seen as a wireless network and connections have to be symmetric there. The goal is to minimise the sum of edge lengths, or for wireless networks, the total power assignment. We define five problems such that they are Euclidean functionals. We show some properties of these functionals, also using their boundary functionals, for arbitrary k, dimension d, and raising edge lengths to the pth power. With these properties we show complete convergence, as well as a bound on the longest edge in an optimal k-edge-connected graph with high probability. We show bounds on the rates of convergence of means for all our functionals. For the functionals associated with k-edge-connectedness we present two umbrella theorems as extensions on a limit theorem. One of the reasons to prove our functionals have these properties is to use partitioning algorithms that rapidly compute near-optimal solutions on typical examples. To explain this performance, we apply smoothed analysis to obtain a smoothed approximation ratio. Mixed integer linear programs are presented for all functionals, which we use for computing optimal solutions. Our computational results show the performance of the partitioning algorithms when we use various numbers of partitions for k-edge-connected graphs and power assignment graphs. These results show that solution times can be decreased greatly while only increasing the solution values slightly if the number of partitons is chosen in the right way. As far as we are aware, k-edge-connectivity and k-vertex-connectivity have not been studied yet as functionals, and no partitioning algorithms have been presented for them. |
| Item Type: | Essay (Master) |
| Faculty: | EEMCS: Electrical Engineering, Mathematics and Computer Science |
| Subject: | 31 mathematics |
| Programme: | Applied Mathematics MSc (60348) |
| Link to this item: | https://purl.utwente.nl/essays/70976 |
| Export this item as: | BibTeX EndNote HTML Citation Reference Manager |
Show download statistics for this publication
Show download statistics for this publicationRepository Staff Only: item control page