Probabilistic properties of highly connected random geometric graphs

We study the probabilistic properties of reliable networks of minimum costs in d-dimensional Euclidean space, with reliability in terms of k-edge-connectivity in graphs. We show that this problem fits into Yukich's framework for Euclidean functionals for arbitrary k, dimension d and distant-power gradient p with p<d. With this framework, several theorems on convergence and concentration of the value of optimal solutions follow. These results are then extended to optimal k-edge-connected power assignment graphs, where we assign transmit power to nodes, and two nodes are connected if they both have sufficient transmit power. This variant models wireless networks. Finally, we devise a partitioning heuristic to find approximate solutions quickly, and we analyze its performance in the framework of smoothed analysis.