Probabilistic Properties of Highly Connected Random Geometric Graphs

Bodo Manthey, Victor Maria Jacobus Johannes Reijnders

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

192 Downloads (Pure)


In this paper, we study the probabilistic properties of reliable networks of minimum costs in d-dimensional Euclidean space. We study 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 results on convergence and concentration of the value of optimal solutions of random inputs follow. These results are then extended to optimal k-edge-connected power assignment graphs, where we assign transmit power to vertices, and two vertices 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
Title of host publicationAlgorithms and Discrete Applied Mathematics - 4th International Conference, CALDAM 2018, Proceedings
Subtitle of host publication4th International Conference, CALDAM 2018, Guwahati, India, February 15-17, 2018, Proceedings
EditorsB.S. Panda, Partha P. Goswami
Number of pages14
ISBN (Electronic)978-3-319-74180-2
ISBN (Print)978-3-319-74179-6
Publication statusPublished - 2018
Event4th Annual Conference on Algorithms and Discrete Applied Mathematics - IIT Guwahati INDIA, Guwahati, India
Duration: 15 Feb 201817 Feb 2018
Conference number: 4

Publication series

NameCommunications in Computer and Information Science
Volume10743 LNCS
ISSN (Print)1865-0929


Conference4th Annual Conference on Algorithms and Discrete Applied Mathematics
Abbreviated titleCALDAM 2018


  • Average-case analysis
  • Connectivity of graphs
  • Random geometric graphs


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

Cite this