Sharp thresholds for monotone properties in random geometric graphs. (English) Zbl 1192.05145
Proceedings of the 36th annual ACM symposium on theory of computing (STOC 2004), Chicago, IL, USA, June 13 - 15, 2004. New York, NY: ACM Press (ISBN 1-58113-852-0). 580-586, electronic only (2004).
MSC:
| 05C80 | Random graphs (graph-theoretic aspects) |
References:
| [1] | Martin J. B. Appel and Ralph P. Russo, The connectivity of a graph on uniform points on {0,1}d, Statistics & Probability Letters, 60 (2002), 351-7. · Zbl 1039.05054 |
| [2] | Lorna Booth, Jehoshua Bruck, Massimo Franceschetti, and Ronald Meester, Covering algorithms, continuum percolation and the geometry of wireless networks, The Annals of Applied Probability, 13 (2003), no. 2, 722-41. · Zbl 1029.60077 |
| [3] | Jean Bourgain and Gil Kalai, Influences of variables and threshold intervals under group symmetries, Geometric Functional Analysis (1997). · Zbl 0982.20004 |
| [4] | Béla Bollobás, Random graphs, Cambridge studies in advanced mathematics, vol. 73, Cambridge University Press, New York, 2001. · Zbl 0979.05003 |
| [5] | Josep Díaz, Mathew D. Penrose, Jordi Petit, and María Sema, Approximating layout problems on geometric random grapphs, Tech. Report TR-417-98, Algorithms and Complexity in Information Technology, 1998. |
| [6] | Richard Durrett, Probability: Theory and Examples, second ed., Duxbury Press, 1996. |
| [7] | Pál Erdos and Alfréd Renyi, On random graphs I, Publicationes Mathimaticae Debrecen (1959). · Zbl 0092.15705 |
| [8] | Pál Erdos and Alfréd Renyi, On the evolution of random graphs, Magyar Tud. Akad. Mat. Kut. Int. Kozl., 5 (1960), 17-61. · Zbl 0103.16301 |
| [9] | Ehud Friedgut and Gil Kalai, Every monotone graph property has a sharp threshold, Proceedings of the American Mathematical Society 124 (1996), 2993-3002. · Zbl 0864.05078 |
| [10] | Erhard Godehardt and Jerzy Jaworski, On the connectivity of a random interval graph, On the connectivity of a random interval graph 9 (1996), no. 1-2, 137-161. 10.1002/(SICI)1098-2418(199608/09)9:1/2 · Zbl 0864.05080 |
| [11] | Piyush Gupta and Panganmala R. Kumar, Stochastic analysis, control, optimization and applications: A volume in honor of W.H. Fleming, ch. Critical power for asymptotic connectivity in wireless networks, Birkhaüser, Boston, 1998. |
| [12] | Piyush Gupta and Panganmala R. Kumar, The capacity of wireless networks, IEEE Transactions on Information Theory IT-46 (2000), no. 2, 388-404. 10.1109/18.825799 · Zbl 0991.90511 |
| [13] | Piyush Gupta and Panganmala R. Kumar, Internets in the sky: The capacity of three dimensional wireless networks, Communications in Information and Systems 1 (2001), no. 1, 33-50. · Zbl 1044.94520 |
| [14] | Erhard Godehardt, Graphs as structural models: the applications of graphs and multigraphs in cluster analysis, Vieweg, Brunswick, 1990. |
| [15] | Alexander Holroyd and Yuval Peres, Trees and matchings from point processes, Electronic communications in probability 8 (2003), no. Paper 3, 17-27. · Zbl 1060.60048 |
| [16] | Jordi Petit i Silvestre, Layout problems, Ph.D. thesis, Universitat Politècnica de Catalunya, Barcelona, 25 May 2001. |
| [17] | Svante Janson, Tomasz Luczak, and Andrzej Ruciński, Random graphs, Wiley-Interscience series in discrete mathematics and optimization, Wiley-Interscience, New York, 2000. · Zbl 0968.05003 |
| [18] | Bhaskar Krishnamachari, Stephen Wicker, Ramon Bejar, and Marc Pearlman, Communications, information and network security, ch. Critical Density Thresholds in Distributed Wireless Networks, Kluwer, December 2002. |
| [19] | Tom Leighton and Peter W. Shor, Tight bounds for minimax grid matching, with applications to the average case analysis of algorithms, Combinatorica 9 (1989), 161-87. · Zbl 0686.68039 |
| [20] | Gregory McColm, Threshold functions for random graphs on a line segment, Submitted for publication. · Zbl 1048.05076 |
| [21] | S. Muthukrishnan and Gopal Pandurangan, The bin-covering technique for thresholding random geometric graph properties, Tech. Report 2003-39, DIMACS, November 2003. |
| [22] | Valery B. Nevzorov, Records: A mathematical theory, Translations of Mathematical Monographs, vol. 194, American Mathematical Society, Providence, Rhode Island, 2001. |
| [23] | Mathew D. Penrose, The longest edge of the random minimal spanning tree, The Annals of Applied Probability 7 (1997), no. 2, 340-61. · Zbl 0884.60042 |
| [24] | Mathew D. Penrose, Random geometric graphs, Oxford Studies in Probability, vol. 5, Oxford University Press, May 2003. · Zbl 1029.60007 |
| [25] | S. Shakkottai, R. Srikant, and N. B. Shroff, Unreliable sensor grids: coverage, connectivity and diameter, Proc. Infocom 2003. 10.1016/j.adhoc.2004.02.001 |
| [26] | Peter W. Shor and Joseph E. Yukich, Minmax grid matching and empirical measures, The Annals of Probability 19 (1991), no. 3, 1338-48. · Zbl 0734.60005 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
