MEETING TIMES OF RANDOM WALKS ON GRAPHS

Warpechowska-Gruca, Jolanta

MEETING TIMES OF RANDOM WALKS ON GRAPHS

dc.contributor.author	Warpechowska-Gruca, Jolanta	eng
dc.date.accessioned	2008-05-20T23:31:28Z
dc.date.available	2008-05-20T23:31:28Z
dc.date.computerscience	1999-05-27	eng
dc.date.issued	1994-02-01	eng
dc.description.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.	eng
dc.description.notes	We are currently acquiring citations for the work deposited into this collection. We recognize the distribution rights of this item may have been assigned to another entity, other than the author(s) of the work.If you can provide the citation for this work or you think you own the distribution rights to this work please contact the Institutional Repository Administrator at digitize@ucalgary.ca	eng
dc.identifier.department	1994-535-04	eng
dc.identifier.doi	http://dx.doi.org/10.11575/PRISM/31330
dc.identifier.uri	http://hdl.handle.net/1880/46555
dc.language.iso	Eng	eng
dc.publisher.corporate	University of Calgary	eng
dc.publisher.faculty	Science	eng
dc.subject	Computer Science	eng
dc.title	MEETING TIMES OF RANDOM WALKS ON GRAPHS	eng
dc.type	unknown
thesis.degree.discipline	Computer Science	eng