The cover time of random geometric graphs |
| |
Authors: | Colin Cooper Alan Frieze |
| |
Institution: | 1. Department of Computer Science, King's College, University of London, London WC2R 2LS, UK;2. Department of Mathematical Sciences, Carnegie Mellon University, Pittsburgh, Pennsylvania 15213 |
| |
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 $\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)=\{\{v,w\}: w\ne v,\,w\in D(v,r)\}$ . 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=(c\log n/(\Upsilon_dn))^{1/d}$ . Then whp the cover time satisfies © 2010 Wiley Periodicals, Inc. Random Struct. Alg., 38, 324–349, 2011 |
| |
Keywords: | random walk cover time ad‐hoc wireless network random geometric graph |
|
|