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

    41 Downloads (Pure)


    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
    Number of pages11
    JournalDiscrete applied mathematics
    Publication statusE-pub ahead of print/First online - 22 May 2019


    • 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