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.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Althaus, E., Călinescu, G., Mandoiu, I.I., Prasad, S., Tchervenski, N., Zelikovsky, A.: Power efficient range assignment for symmetric connectivity in static ad hoc wireless networks. Wireless Netw. 12(3), 287–299 (2006)
Bendali, F., Diarrassouba, I., Mahjoub, A.R., Didi Biha, M., Mailfert, J.: A branch-and-cut algorithm for the k-edge connected subgraph problem. Networks 55(1), 13–32 (2010)
Bettstetter, C.: On the minimum node degree and connectivity of a wireless multihop network. In: Proceedings of the 3rd ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc), pp. 80–91. ACM (2002)
Bläser, M., Manthey, B., Rao, B.V.R.: Smoothed analysis of partitioning algorithms for euclidean functionals. Algorithmica 66(2), 397–418 (2013)
Clementi, A.E.F., Penna, P., Silvestri, R.: On the power assignment problem in radio networks. Mob. Netw. Appl. 9(2), 125–140 (2004)
Calinescu, G., Wan, P.-J.: Range assignment for high connectivity in wireless ad hoc networks. In: Pierre, S., Barbeau, M., Kranakis, E. (eds.) ADHOC-NOW 2003. LNCS, vol. 2865, pp. 235–246. Springer, Heidelberg (2003). https://doi.org/10.1007/978-3-540-39611-6_21
Czumaj, A., Lingas, A.: On approximability of the minimum-cost k-connected spanning subgraph problem. In: Tarjan, R.E., Warnow, T.J. (eds.) Proceedings of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 281–290. ACM/SIAM (1999)
Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness (1979)
de Graaf, M., Manthey, B.: Probabilistic analysis of power assignments. Random Struct. Algorithms 51(3), 483–505 (2017)
Grötschel, M., Monma, C.L., Stoer, M.: Polyhedral approaches to network survivability. In: Roberts, F., Hwang, F., Monma, C.L. (eds.) Proceedings of the Workshop on Reliability of Computer and Communication Networks. Series in Discrete Mathematics and Theoretical Computer Science, vol. 5, pp. 121–141. American Mathematical Society (1991)
Hsu, P.L., Robbins, H.: Complete convergence and the law of large numbers. Proc. Nat. Acad. Sci. 33(2), 25–31 (1947)
Kammer, F., Täubig, H.: Connectivity. In: Brandes, U., Erlebach, T. (eds.) Network Analysis. LNCS, vol. 3418, pp. 143–177. Springer, Heidelberg (2005). https://doi.org/10.1007/978-3-540-31955-9_7
Khuller, S., Vishkin, U.: Biconnectivity approximations and graph carvings. J. ACM 41(2), 214–235 (1994)
Manthey, B., Röglin, H.: Smoothed analysis: analysis of algorithms beyond worst case. IT – Inf. Technol. 53(6), 280–286 (2011)
Matula, D.W.: The cohesive strength of graphs. In: Chartrand, G., Kapoor, S.F. (eds.) The Many Facets of Graph Theory. LNM, vol. 110, pp. 215–221. Springer, Heidelberg (1969). https://doi.org/10.1007/BFb0060120
Redmond, C.: Boundary rooted graphs and euclidean matching algorithms. Ph.D. thesis, Lehigh University, Bethlehem, PA, USA (1993)
Rhee, W.T.: A matching problem and subadditive euclidean functionals. Ann. Appl. Probab. 3(3), 794–801 (1993)
Santi, P., Blough, D.M., Vainstein, F.: A probabilistic analysis for the range assignment problem in ad hoc networks. In: Proceedings of the 2nd ACM International Symposium on Mobile Ad Hoc Networking and Computing, pp. 212–220. ACM (2001)
Spielman, D.A., Teng, S.H.: Smoothed analysis: an attempt to explain the behavior of algorithms in practice. Commun. ACM 52(10), 76–84 (2009)
Yukich, J.E.: Probability Theory of Classical Euclidean Optimization Problems. LNM, vol. 1675. Springer, Heidelberg (1998). https://doi.org/10.1007/BFb0093472
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2018 Springer International Publishing AG
About this paper
Cite this paper
Manthey, B., Reijnders, V.M.J.J. (2018). Probabilistic Properties of Highly Connected Random Geometric Graphs. In: Panda, B., Goswami, P. (eds) Algorithms and Discrete Applied Mathematics. CALDAM 2018. Lecture Notes in Computer Science(), vol 10743. Springer, Cham. https://doi.org/10.1007/978-3-319-74180-2_5
Download citation
DOI: https://doi.org/10.1007/978-3-319-74180-2_5
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-74179-6
Online ISBN: 978-3-319-74180-2
eBook Packages: Computer ScienceComputer Science (R0)