Probabilistic Properties of Highly Connected Random Geometric Graphs

Research output: Contribution to conferenceAbstract

46 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

    Reijnders, V. M. J. J., & Manthey, B. (2017). Probabilistic Properties of Highly Connected Random Geometric Graphs. 105-108. Abstract from 15th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, CTW 2017, Cologne, Germany.