The cover time of random geometric graphs

ABSTRACT

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 ϒ_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) = {{v, w}: w ≠ v, w ∈ D(v, r)}. Let G(d, r, n), d ≥ 3 be a random geometric graph. Let c > 1 be constant, and let r = (c log n/(ϒ_dn))^1/d. Then whp

C_G ~ clog(c/c-1)nlogn.

REFERENCES

• 1: D. Aldous and J. Fill. Reversible Markov Chains and Random Walks on Graphs.
• 2: Romas Aleliunas , Richard M. Karp , Richard J. Lipton , Laszlo Lovasz , Charles Rackoff, Random walks, universal traversal sequences, and the complexity of maze problems, Proceedings of the 20th Annual Symposium on Foundations of Computer Science, p.218-223, October 29-31, 1979
• 3: Chen Avin , Gunes Ercal, On the cover time and mixing time of random geometric graphs, Theoretical Computer Science, v.380 n.1-2, p.2-22, July 2007 [doi>10.1016/j.tcs.2007.02.065]
• 4: A. K. Chandra , P. Raghavan , W. L. Ruzzo , R. Smolensky, The electrical resistance of a graph captures its commute and cover times, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.574-586, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73062]
• 5: Colin Cooper , Alan Frieze, The Cover Time of Random Regular Graphs, SIAM Journal on Discrete Mathematics, v.18 n.4, p.728-740, 2005 [doi>10.1137/S0895480103428478]
• 6: Colin Cooper , Alan Frieze, The cover time of the preferential attachment graph, Journal of Combinatorial Theory Series B, v.97 n.2, p.269-290, March, 2007 [doi>10.1016/j.jctb.2006.05.007]
• 7: Colin Cooper , Alan Frieze, The cover time of sparse random graphs, Random Structures & Algorithms, v.30 n.1-2, p.1-16, January 2007 [doi>10.1002/rsa.v30:1/2]
• 8: Colin Cooper , Alan Frieze, The cover time of the giant component of a random graph, Random Structures & Algorithms, v.32 n.4, p.401-439, July 2008 [doi>10.1002/rsa.v32:4]
• 9: Colin Cooper , Alan Frieze, The Cover Time of Random Digraphs, Proceedings of the 10th International Workshop on Approximation and the 11th International Workshop on Randomization, and Combinatorial Optimization. Algorithms and Techniques, August 20-22, 2007, Princeton, NJ, USA [doi>10.1007/978-3-540-74208-1_31]
• 10: P. G. Doyle and J. L. Snell Random Walks and Electrical Networks. Carus Mathematical Monograph 22, AMA (1984).
• 11: R. Durrett, Probability: Theory and Examples, Brooks/Cole 1991.
• 12: Uriel Feige, A tight upper bound on the cover time for random walks on graphs, Random Structures & Algorithms, v.6 n.1, p.51-54, Jan. 1995 [doi>10.1002/rsa.3240060106]
• 13: Uriel Feige, A tight lower bound on the cover time for random walks on graphs, Random Structures & Algorithms, v.6 n.4, p.433-438, July 1995 [doi>10.1002/rsa.3240060406]
• 14: P. Gupta and P. R. Kumar, Critical power for asymptotic connectivity in wireless networks, In Stochastic Analysis, Control, Optimization and Applications, Birkhaüser, Boston, 1998.
• 15: P. Gupta and P. R. Kumar, Internets in the sky: the capacity of three dimensional wireless networks. Communications in Information and Systems, 1 (2001) 33--50.
• 16: Mark Jerrum , Alistair Sinclair, The Markov chain Monte Carlo method: an approach to approximate counting and integration, Approximation algorithms for NP-hard problems, PWS Publishing Co., Boston, MA, 1996
• 17: M. D. Penrose. Random Geometric Graphs. Oxford University Press (2003).
• 18: A. Sinclair. Improved bounds for mixing rates of Markov chains and multicommodity flow. Combinatorics, probability and Computing, 1 (1992), 351--370.
• 19: Feng Xue , P. R. Kumar, Scaling laws for ad hoc wireless networks: an information theoretic approach, Foundations and Trends® in Networking, v.1 n.2, p.145-270, July 2006 [doi>10.1561/1300000002]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

Additional Classification:
  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Analysis of algorithms