Probabilistic Properties of Highly Connected Random Geometric Graphs

Bodo  Manthey; Victor Maria Jacobus Johannes Reijnders

doi:10.1007/978-3-319-74180-2_5

Probabilistic Properties of Highly Connected Random Geometric Graphs

Bodo Manthey, Victor Maria Jacobus Johannes Reijnders

Discrete Mathematics and Mathematical Programming

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

204 Downloads (Pure)

Abstract

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 language	English
Title of host publication	Algorithms and Discrete Applied Mathematics - 4th International Conference, CALDAM 2018, Proceedings
Subtitle of host publication	4th International Conference, CALDAM 2018, Guwahati, India, February 15-17, 2018, Proceedings
Editors	B.S. Panda, Partha P. Goswami
Publisher	Springer
Pages	59-72
Number of pages	14
ISBN (Electronic)	978-3-319-74180-2
ISBN (Print)	978-3-319-74179-6
DOIs	https://doi.org/10.1007/978-3-319-74180-2_5
Publication status	Published - 2018
Event	4th Annual Conference on Algorithms and Discrete Applied Mathematics - IIT Guwahati INDIA, Guwahati, India Duration: 15 Feb 2018 → 17 Feb 2018 Conference number: 4

Publication series

Name	Communications in Computer and Information Science
Volume	10743 LNCS
ISSN (Print)	1865-0929

Conference

Conference	4th Annual Conference on Algorithms and Discrete Applied Mathematics
Abbreviated title	CALDAM 2018
Country/Territory	India
City	Guwahati
Period	15/02/18 → 17/02/18

Keywords

Average-case analysis
Connectivity of graphs
Random geometric graphs

Access to Document

10.1007/978-3-319-74180-2_5Licence: Unspecified

ProbabilisticHighConnAccepted author version, 287 KB

Cite this

Manthey, B., & Reijnders, V. M. J. J. (2018). Probabilistic Properties of Highly Connected Random Geometric Graphs. In B. S. Panda, & P. P. Goswami (Eds.), Algorithms and Discrete Applied Mathematics - 4th International Conference, CALDAM 2018, Proceedings: 4th International Conference, CALDAM 2018, Guwahati, India, February 15-17, 2018, Proceedings (pp. 59-72). (Communications in Computer and Information Science; Vol. 10743 LNCS). Springer. https://doi.org/10.1007/978-3-319-74180-2_5

Manthey, Bodo ; Reijnders, Victor Maria Jacobus Johannes. / Probabilistic Properties of Highly Connected Random Geometric Graphs. Algorithms and Discrete Applied Mathematics - 4th International Conference, CALDAM 2018, Proceedings: 4th International Conference, CALDAM 2018, Guwahati, India, February 15-17, 2018, Proceedings. editor / B.S. Panda ; Partha P. Goswami. Springer, 2018. pp. 59-72 (Communications in Computer and Information Science).

@inproceedings{2ae2dc44aac04b2b960e2857ea255428,

title = "Probabilistic Properties of Highly Connected Random Geometric Graphs",

abstract = "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{\textquoteright}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.",

keywords = "Average-case analysis, Connectivity of graphs, Random geometric graphs",

author = "Bodo Manthey and Reijnders, {Victor Maria Jacobus Johannes}",

year = "2018",

doi = "10.1007/978-3-319-74180-2_5",

language = "English",

isbn = "978-3-319-74179-6",

series = "Communications in Computer and Information Science",

publisher = "Springer",

pages = "59--72",

editor = "B.S. Panda and Goswami, {Partha P. }",

booktitle = "Algorithms and Discrete Applied Mathematics - 4th International Conference, CALDAM 2018, Proceedings",

address = "Germany",

note = "4th Annual Conference on Algorithms and Discrete Applied Mathematics, CALDAM 2018 ; Conference date: 15-02-2018 Through 17-02-2018",

}

Manthey, B & Reijnders, VMJJ 2018, Probabilistic Properties of Highly Connected Random Geometric Graphs. in BS Panda & PP Goswami (eds), Algorithms and Discrete Applied Mathematics - 4th International Conference, CALDAM 2018, Proceedings: 4th International Conference, CALDAM 2018, Guwahati, India, February 15-17, 2018, Proceedings. Communications in Computer and Information Science, vol. 10743 LNCS, Springer, pp. 59-72, 4th Annual Conference on Algorithms and Discrete Applied Mathematics, Guwahati, India, 15/02/18. https://doi.org/10.1007/978-3-319-74180-2_5

Probabilistic Properties of Highly Connected Random Geometric Graphs. / Manthey, Bodo ; Reijnders, Victor Maria Jacobus Johannes.
Algorithms and Discrete Applied Mathematics - 4th International Conference, CALDAM 2018, Proceedings: 4th International Conference, CALDAM 2018, Guwahati, India, February 15-17, 2018, Proceedings. ed. / B.S. Panda; Partha P. Goswami. Springer, 2018. p. 59-72 (Communications in Computer and Information Science; Vol. 10743 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Probabilistic Properties of Highly Connected Random Geometric Graphs

AU - Manthey, Bodo

AU - Reijnders, Victor Maria Jacobus Johannes

N1 - Conference code: 4

PY - 2018

Y1 - 2018

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

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

KW - Average-case analysis

KW - Connectivity of graphs

KW - Random geometric graphs

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

U2 - 10.1007/978-3-319-74180-2_5

DO - 10.1007/978-3-319-74180-2_5

M3 - Conference contribution

SN - 978-3-319-74179-6

T3 - Communications in Computer and Information Science

SP - 59

EP - 72

BT - Algorithms and Discrete Applied Mathematics - 4th International Conference, CALDAM 2018, Proceedings

A2 - Panda, B.S.

A2 - Goswami, Partha P.

PB - Springer

T2 - 4th Annual Conference on Algorithms and Discrete Applied Mathematics

Y2 - 15 February 2018 through 17 February 2018

ER -

Manthey B, Reijnders VMJJ. Probabilistic Properties of Highly Connected Random Geometric Graphs. In Panda BS, Goswami PP, editors, Algorithms and Discrete Applied Mathematics - 4th International Conference, CALDAM 2018, Proceedings: 4th International Conference, CALDAM 2018, Guwahati, India, February 15-17, 2018, Proceedings. Springer. 2018. p. 59-72. (Communications in Computer and Information Science). doi: 10.1007/978-3-319-74180-2_5

Probabilistic Properties of Highly Connected Random Geometric Graphs

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this