Abstract
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.
Original language | English |
---|---|
Pages | 105-108 |
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 http://ctw.uni-koeln.de/ |
Conference
Conference | 15th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, CTW 2017 |
---|---|
Abbreviated title | CTW |
Country/Territory | Germany |
City | Cologne |
Period | 6/06/17 → 8/06/17 |
Internet address |