ALBERT — All Library Books, journals and Electronic Records Telegrafenberg

Hits per page

hit 1 - 1 | 1 hit

Select All Export

Electronic Resource

On the cover time of random walks on graphs (1989)

Kahn, Jeff D. ; Linial, Nathan ; Nisan, Noam ; [et al.]

Springer

Journal of theoretical probability 2 (1989), S. 121-128

add to mindlist on the mindlist

Details

ISSN: 1572-9230

Keywords: Random walks ; cover times ; graphs ; infinite graphs ; trees

Source: Springer Online Journal Archives 1860-2000

Topics: Mathematics

Notes: Abstract This article deals with random walks on arbitrary graphs. We consider the cover time of finite graphs. That is, we study the expected time needed for a random walk on a finite graph to visit every vertex at least once. We establish an upper bound ofO(n 2) for the expectation of the cover time for regular (or nearly regular) graphs. We prove a lower bound of Ω(n logn) for the expected cover time for trees. We present examples showing all our bounds to be tight.

Type of Medium: Electronic Resource

URL: http://dx.doi.org/10.1007/BF01048274

	Location	Call Number	Expected	Availability

Others were also interested in ...

Paper (German National Licenses)

Fulltext

hit 1 - 1 | 1 hit