Probabilistic properties of highly connected random geometric graphs

Bodo Manthey*, Victor M.J.J. Reijnders

*Corresponding author for this work

Research output: Contribution to journalArticleAcademicpeer-review

47 Downloads (Pure)

Abstract

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.

Original languageEnglish
Pages (from-to)366-376
Number of pages11
JournalDiscrete applied mathematics
Early online date22 May 2019
DOIs
Publication statusPublished - 31 Dec 2021

Keywords

  • Euclidean optimization problems
  • Power assignments
  • Probabilistic analysis

Fingerprint

Dive into the research topics of 'Probabilistic properties of highly connected random geometric graphs'. Together they form a unique fingerprint.

Cite this