This web page contains the abstract of my paper:
"Random Walks on Regular and Irregular Graphs", with D. Coppersmith and U. Feige, Siam J. Discrete Math., 9(1996), p. 301-308.
Abstract: For an undirected graph and a optimal cyclic list of all its vertices, the cyclic cover time is the expected time it takes a simple random walk to travel from vertex to vertex along the list, until it completes a full cycle. The main result of this paper is a characterization of the cyclic cover time in terms of simple and easy to compute graph properties. Namely, for any connected graph, the cyclic cover time is theta(n*n*ave(d)*ave(1/d)) where n is the number of vertices in the graph, ave(d) is the average degree of its vertices and ave(1/d) is the average of the inverse of the degree of its vertices. Other results obtained in the processes of proving the main theorem are a similar characterization of minimum resistance spanning trees of graphs, improved bounds on the cover time of graphs, and a simplified proof that the maximum commute time in any connected graph is at most (4*n**3)/27 + o(n**3).
IBM Research home page |
James B. Shearer's home page |
[ IBM home page | Order | Search | Contact IBM | Help | (C) | (TM) ]