A technique for lower bounding the cover time

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A technique for lower bounding the cover time

Full text

Pdf (461 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the twenty-second annual ACM symposium on Theory of computing table of contents

Baltimore, Maryland, United States

Pages: 254 - 259

Year of Publication: 1990

ISBN:0-89791-361-2

Author

D. Zuckerman

Division of Computer Science, University of California, Berkeley, CA

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 5, Downloads (12 Months): 27, Citation Count: 6

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/100216.100249 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	A1	D.J. Aldous, On the time taken by random walks on finite groups to visit every state, Z. Wahrsch. Verw. Gebiete, 62 (1983), pp. 361- 374.
	A2	D.J. Aldous, Hitting times for random walks on vertex transitive graphs, Math. Proc. Cambridge Phil. Soc., 106 (1989), pp. 179-191.
	A3	D.J. Aldous, Lower bounds for covering times for reversible Markov chains and random walks on graphs, J. Theoretical Probab., 2 (1989), pp. 91-100.
	A4	D.J. Aldous, Random walks on large graphs: a survey, Unpublished, 1988.
	A5	D.J. Aldous, Random walk covering of some special trees, J. Math. Anal. Appl., to appear.
	A6	D.J. Aldous, Personal communication, 1989.
	AK*	R. Aleliunas, R.M. Karp, R.J. Lipton, L. Lovasz, and C. Rackoff, Random walks, universal traversal sequences, and the complexity of maze problems, Proc. 20th Annual IEEE Symposium on Foundations of Computer Science, 1979, pp. 218-233.
	AKS	M. Ajtai , J. Komlos , E. Szemeredi, Deterministic simulation in LOGSPACE, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.132-140, January 1987, New York, New York, United States [doi>10.1145/28395.28410]
	BC	S. Bhatt and J.Y. Cat, Take a walk, grow a tree, Proc. 29th Annual IEEE Symposium on Foundations of Computer Science, 1988, pp. 469-478.
	BK	A. Broder and A.R. Karlin, Bounds on covering times, J. Theoretical Probab., 2 (1989), pp. 101-120.
	C	J.T. Cox, Coalescing random walks and voter model consensus times on the lotus, Ann. Probab., 17 (1989), pp. 1333-1366.
	CR*	A. K. Chandra , P. Raghavan , W. L. Ruzzo , R. Smolensky, The electrical resistance of a graph captures its commute and cover times, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.574-586, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73062]
	DFK	M. Dyer , A. Frieze, A random polynomial time algorithm for approximating the volume of convex bodies, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.375-381, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73043]
	DS	L. Devroye and A. Sbihi, Inequalities for random walks on trees, Technical Report, McGill University, 1989.
	JS	Mark Jerrum , Alistair Sinclair, Conductance and the rapid mixing property for Markov chains: the approximation of permanent resolved, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.235-244, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62234]
	KL*	J.D. Kahn, N. Linial, N. Nisan, and M.E. Saks, On the cover time of random walks in graphs, J. Theoretical Probab., 2 (1989), pp. 121-28.
	K	J. Keilson, Markov Chain Models - Rarity and Exponentiality, Springer-Verlag, 1979.
	KS	J.G. Kemeny and J.L. Snell, Finite Markov Chains, Van Nostrand, 1969.
	Ma	P.C. Matthews, Covering problems for Brownian motion on spheres, Ann. Probab., 16 (1988), pp. 189-199.
	Mo	J.W. Moon, Random walks on random trees, J. Austral. Math. Soc., 15 (1973), pp. 42-53.
	Z	D. Zuckerman, Covering times of random walks on bounded degree trees and other graphs, J. Theoretical Probab., 2 (1989), pp. 147-57.

CITED BY 6

	Greg Barnes , Uriel Feige, Short random walks on graphs, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.728-737, May 16-18, 1993, San Diego, California, United States
	Chen Avin , Carlos Brito, Efficient and robust query processing in dynamic environments using random walk techniques, Proceedings of the third international symposium on Information processing in sensor networks, April 26-27, 2004, Berkeley, California, USA
	Noga Alon , Chen Avin , Michal Koucky , Gady Kozma , Zvi Lotker , Mark R. Tuttle, Many random walks are faster than one, Proceedings of the twentieth annual symposium on Parallelism in algorithms and architectures, June 14-16, 2008, Munich, Germany
	Chen Avin , Bhaskar Krishnamachari, The power of choice in random walks: an empirical study, Proceedings of the 9th ACM international symposium on Modeling analysis and simulation of wireless and mobile systems, October 02-06, 2006, Terromolinos, Spain
	Chen Avin , Gunes Ercal, On the cover time and mixing time of random geometric graphs, Theoretical Computer Science, v.380 n.1-2, p.2-22, June, 2007
	Chen Avin , Bhaskar Krishnamachari, The power of choice in random walks: An empirical study, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.52 n.1, p.44-60, January, 2008