Please use this identifier to cite or link to this item: http://hdl.handle.net/1880/46555
Title: MEETING TIMES OF RANDOM WALKS ON GRAPHS
Authors: Warpechowska-Gruca, Jolanta
Keywords: Computer Science
Issue Date: 1-Feb-1994
Abstract: We derive techniques for proving exact values or bounds on the meeting time. These techniques are used to prove two upper bounds on the meeting time of an arbitrary number of random walks in any connected undirected graph. Both bounds express the meeting time of several random walks in terms of the meeting times of fewer random walks. One of the bounds is tight on rings, the other is a generalization of a bound suggested by Tetali and Winkler. The techniques yield exact expressions for the meeting times on rings and for two or three random walks in hitting-time-symmetric graphs. Additional results include case study of various meeting time games on rings, several counterexamples to "natural" conjectures concerning meeting times, and partial characterization of hitting-time-symmetric graphs.
URI: http://hdl.handle.net/1880/46555
Appears in Collections:Technical Reports

Files in This Item:
File Description SizeFormat 
1994-535-04.pdf138.59 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.