×

The cover time of random geometric graphs. (English) Zbl 1219.05174

Summary: We study the cover time of random geometric graphs. Let \(I(d)= [0, 1]^d\) denote the unit torus in \(d\) dimensions. Let \(D(x,r)\) denote the ball (disc) of radius \(r\). Let \(\Upsilon_d\) be the volume of the unit ball \(D(0, 1)\) in \(d\) dimensions. A random geometric graph \(G= G(d,r,n)\) in \(d\) dimensions is defined as follows: Sample \(n\) points \(V\) independently and uniformly at random from \(I(d)\). For each point \(x\) draw a ball \(D(x,r)\) of radius \(r\) about \(x\). The vertex set \(V(G)= V\) and the edge set \(E(G)= \left\{\{v,w\}: w\neq v,\,w\in D(v,r)\right\}\). Let \(G(d,r,n)\), \(d\geq 3\) be a random geometric graph. Let \(C_G\) denote the cover time of a simple random walk on \(G\). Let \(c> 1\) be constant, and let \(r= \left(c\log n/(\Upsilon_d n)\right)^{I/d}\). Then \(\mathbf{whp}\) the cover time satisfies
\[ C_G \sim c\log \left(\frac{c}{c-1}\right) n\log n. \]

MSC:

05C80 Random graphs (graph-theoretic aspects)
05C81 Random walks on graphs
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] D. Aldous J. Fill Reversible Markov chains and random walks on graphs http://stat-www.berkeley.edu/pub/users/aldous/RWG/book.html
[2] R. Aleliunas R. M. Karp R. J. Lipton L. Lovász C. Rackoff 1979 218 223
[3] Avin, On the cover time and mixing time of random geometric graphs, Theor Comput Sci 380 pp 2– (2007) · Zbl 1115.68167 · doi:10.1016/j.tcs.2007.02.065
[4] Ball, Flavors of geometry, Math Sci Res Inst Publ Vol. 31 pp 1– (1997)
[5] Z. Bar-Yossef R. Friedman G. Kliot RaWMS-random walk based lightweight membership service for wireless ad hoc networks 2008
[6] S. Boyd A. Ghosh B. Prabhakar D. Shah Mixing times for random walks on geometric random graphs 2005
[7] Brown, Complex variables and applications (1996)
[8] Cooper, The cover time of random regular graphs, SIAM J Discrete Math 18 pp 728– (2005) · Zbl 1075.05079 · doi:10.1137/S0895480103428478
[9] Cooper, The cover time of the preferential attachment graph, J Combin Theor B 97 pp 269– (2007) · Zbl 1114.05095 · doi:10.1016/j.jctb.2006.05.007
[10] Cooper, The cover time of sparse random graphs, Random Struct Algorithm 30 pp 1– (2007) · Zbl 1113.05089 · doi:10.1002/rsa.20151
[11] Cooper, The cover time of the giant component of a random graph, Random Struct Algorithm 32 pp 401– (2008) · Zbl 1157.05045 · doi:10.1002/rsa.20201
[12] C. Cooper A. M. Frieze The cover time of random digraphs 2007 422 435 · Zbl 1171.05417
[13] Doyle, Random walks and electrical networks (1984) · Zbl 0583.60065
[14] Durrett, Probability: Theory and examples (1991)
[15] Feige, A tight upper bound for the cover time of random walks on graphs, Random Struct Algorithm 6 pp 51– (1995) · Zbl 0811.60060 · doi:10.1002/rsa.3240060106
[16] Feige, A tight lower bound for the cover time of random walks on graphs, Random Struct Algorithm 6 pp 433– (1995) · Zbl 0832.60016 · doi:10.1002/rsa.3240060406
[17] Feller, An Introduction to Probability Theory I (1960) · Zbl 0039.13201
[18] Gupta, Stochastic analysis, control, optimization and applications: A volume Honor of W. H. Fleming pp 547– (1998)
[19] Gupta, Internets in the sky: The capacity of three dimensional wireless networks, Comm Inform Syst 1 pp 33– (2001) · Zbl 1044.94520 · doi:10.4310/CIS.2001.v1.n1.a3
[20] Lovász, Random walks on graphs: A survey, Bolyai Society Mathematical Studies, Combinatorics, Paul Erdös is Eighty 2 pp 1– (1993)
[21] Penrose, Random geometric graphs (2003) · Zbl 1029.60007 · doi:10.1093/acprof:oso/9780198506263.001.0001
[22] Sinclair, Improved bounds for mixing rates of Markov chains and multicommodity flow, Combinator Probab Comput 1 pp 351– (1992) · Zbl 0801.90039 · doi:10.1017/S0963548300000390
[23] Wilf, Generatingfunctionology (1990)
[24] Xue, Scaling laws for ad hoc wireless networks: An information theoretic approach, Found Trends Networking 1 pp 145– (2006) · doi:10.1561/1300000002
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.