Random Geometric Graph Diameter in the Unit Disk with ℓp Metric (Extended Abstract)

Ellis, Robert and Martin, Jeremy and Yan, Catherine (2004) Random Geometric Graph Diameter in the Unit Disk with ℓp Metric (Extended Abstract). In: Graph Drawing 12th International Symposium, GD 2004, September 29-October 2, 2004, New York, NY, USA , pp. 167-172 (Official URL: http://dx.doi.org/10.1007/978-3-540-31843-9_18).

Full text not available from this repository.

Abstract

Let n be a positive integer, λ> 0 a real number, and 1≤ p≤ ∞. We study the unit disk random geometric graphG p (λ,n), defined to be the random graph on n vertices, independently distributed uniformly in the standard unit disk in R2, with two vertices adjacent if and only if their ℓ p -distance is at most λ. Let λ = c ln n/n, and let ap be the ratio of the (Lebesgue) areas of the ℓ p- and ℓ2-unit disks. Almost always, G p (λ,n) has no isolated vertices and is also connected if c>a p − − 1/2, and has n1−apc2(1+o(1)) isolated vertices if c<ap–1/2. Furthermore, we find upper bounds (involving λ but independent of p) for the diameter of G p (λ,n), building on a method originally due to M. Penrose.

Item Type:Conference Paper
Additional Information:10.1007/978-3-540-31843-9_18
Classifications:A General Literature > A.001 Introductory and Survey
ID Code:583

Repository Staff Only: item control page

References

Chen, X., Jia, X.: Package routing algorithms in mobile ad-hoc wireless networks. In: 2001 International Conference on Parallel Processing Workshops. (2001) 485-490.

Stojmenovic, I., Seddoigh, M., Zunic, J.: Dominating sets and neighbor elimination-based broadcasting algorithms in wireless networks. IEEE Trans. Parallel Distrib. Syst. 13 (2002) 14-25.

Wu, J., Li, H.: A dominating-set-based routing scheme in ad hoc wireless networks. Telecommunication Systems 18 (2001) 13-36.

Ellis, R.B., Jia, X., Yan, C.H.: On random ponts in the unit disk. (preprint)

Whittaker, E.T., Watson, G.N.: A course of modern analysis. Cambridge University Press (1996).

Penrose, M.D.: On k-connectivity for a geometric random graph. Random Structures Algorithms 15 (1999) 145-164.

Alon, N., Spencer, J.H.: The probabilistic method. 2nd edn. John Wiley (2000).

Klarner, D.A.: Cell growth problems. Canad. J. Math. 19 (1967) 851-863.