In this paper we study the probabilistic properties of reliable networks of minimal total edge lengths. We study reliability in terms of k-edge-connectivity in graphs in d-dimensional space. We show 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 the convergence of optimal solutions follow. We apply Yukich’s framework for functionals so that we can use partitioning algorithms that rapidly compute near-optimal solutions on typical examples. These results are then extended to optimal k-edge-connected power assignment graphs, where we assign power to vertices and charge per vertex. The network can be modelled as a wireless network.
|Number of pages||4|
|Publication status||Published - 6 Jun 2017|
|Event||15th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, CTW 2017 - Cologne, Germany|
Duration: 6 Jun 2017 → 8 Jun 2017
Conference number: 15
|Conference||15th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, CTW 2017|
|Period||6/06/17 → 8/06/17|