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

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

    Fingerprint

    Random Geometric Graph
    Wireless networks
    Costs
    Edge-connectivity
    Graph in graph theory
    Vertex of a graph
    Wireless Networks
    Assign
    Euclidean space
    Partitioning
    Euclidean
    Approximate Solution
    Assignment
    Optimal Solution
    Heuristics
    Sufficient
    Gradient
    Arbitrary
    Theorem
    Framework

    Keywords

    • Euclidean optimization problems
    • Power assignments
    • Probabilistic analysis

    Cite this

    @article{1621e0148c0a4d08942afdc5297e1065,
    title = "Probabilistic properties of highly connected random geometric graphs",
    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",
    keywords = "Euclidean optimization problems, Power assignments, Probabilistic analysis",
    author = "Bodo Manthey and Reijnders, {Victor M.J.J.}",
    year = "2019",
    month = "5",
    day = "22",
    doi = "10.1016/j.dam.2019.04.007",
    language = "English",
    journal = "Discrete applied mathematics",
    issn = "0166-218X",
    publisher = "Elsevier",

    }

    Probabilistic properties of highly connected random geometric graphs. / Manthey, Bodo; Reijnders, Victor M.J.J.

    In: Discrete applied mathematics, 22.05.2019.

    Research output: Contribution to journalArticleAcademicpeer-review

    TY - JOUR

    T1 - Probabilistic properties of highly connected random geometric graphs

    AU - Manthey, Bodo

    AU - Reijnders, Victor M.J.J.

    PY - 2019/5/22

    Y1 - 2019/5/22

    N2 - 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

    AB - 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

    KW - Euclidean optimization problems

    KW - Power assignments

    KW - Probabilistic analysis

    UR - http://www.scopus.com/inward/record.url?scp=85065832515&partnerID=8YFLogxK

    UR - https://www.sciencedirect.com/science/article/pii/S0166218X19302173?via%3Dihub

    U2 - 10.1016/j.dam.2019.04.007

    DO - 10.1016/j.dam.2019.04.007

    M3 - Article

    AN - SCOPUS:85065832515

    JO - Discrete applied mathematics

    JF - Discrete applied mathematics

    SN - 0166-218X

    ER -