Probabilistic Properties of Highly Connected Random Geometric Graphs

Research output: Contribution to conferenceAbstractOther research output

63 Downloads (Pure)

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 languageEnglish
Pages105-108
Number of pages4
Publication statusPublished - 6 Jun 2017
Event15th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, CTW 2017 - Cologne, Germany
Duration: 6 Jun 20178 Jun 2017
Conference number: 15
http://ctw.uni-koeln.de/

Conference

Conference15th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, CTW 2017
Abbreviated titleCTW
CountryGermany
CityCologne
Period6/06/178/06/17
Internet address

Fingerprint

Dive into the research topics of 'Probabilistic Properties of Highly Connected Random Geometric Graphs'. Together they form a unique fingerprint.

Cite this