The cover time of sparse random graphs.

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

The cover time of sparse random graphs.

Full text

Pdf (498 KB)

Source

Symposium on Discrete Algorithms archive
Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms table of contents

Baltimore, Maryland

SESSION: Session 3B table of contents

Pages: 140 - 147

Year of Publication: 2003

ISBN:0-89871-538-5

Authors

Colin Cooper	Goldsmiths College, London, UK
Alan Frieze	Carnegie Mellon University, Pittsburgh

Sponsors

: SIAM Activity Group on Discrete Mathematics
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

Society for Industrial and Applied Mathematics Philadelphia, PA, USA

Bibliometrics

Downloads (6 Weeks): 3, Downloads (12 Months): 39, Citation Count: 9

Additional Information:

abstract references cited by index terms collaborative colleagues

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

ABSTRACT

We study the cover time of a random walk on graphs G ∈ Gn, p when p = c log n/n, c < 1. We prove that whpthe cover time is asymptotic to c log (c/c--1) n log n.

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.

	1	R. Aleliunas, R.M. Karp, R.J. Lipton, L. Lovász and C. Rackoff, Random Walks, Universal Traversal Sequences, and the Complexity of Maze Problems. Proceedings of the 20th Annual IEEE Symposium on Foundations of Computer Science (1979) 218--223.
	2	B. Bollobás, Random graphs (Second edition), Cambridge University Press (2001).
	3	B. Bollobás , A. M. Frieze , T. I. Fenner, An algorithm for finding Hamilton paths and cycles in random graphs, Combinatorica, v.7 n.4, p.327-341, Dec, 1987 [doi>10.1007/BF02579321]
	4	Colin Cooper , Alan Frieze, Crawling on web graphs, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509970]
	5	P. Erdös and A. Rényi, On random graphs I, Publ. Math. Debrecen 6 (1959) 290--297.
	6	Uriel Feige, A tight upper bound on the cover time for random walks on graphs, Random Structures & Algorithms, v.6 n.1, p.51-54, Jan. 1995 [doi>10.1002/rsa.3240060106]
	7	Uriel Feige, A tight lower bound on the cover time for random walks on graphs, Random Structures & Algorithms, v.6 n.4, p.433-438, July 1995 [doi>10.1002/rsa.3240060406]
	8	S. Janson, T. Luczak and A. Ruciński, Random graphs, Wiley (2000).
	9	Mark Jerrum , Alistair Sinclair, The Markov chain Monte Carlo method: an approach to approximate counting and integration, Approximation algorithms for NP-hard problems, PWS Publishing Co., Boston, MA, 1996
	10	Johan Jonasson, On the Cover Time for Random Walks on Random Graphs, Combinatorics, Probability and Computing, v.7 n.3, p.265-279, September 1998 [doi>10.1017/S0963548398003538]

CITED BY 9

	Colin Cooper , Alan Frieze, The cover time of two classes of random graphs, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
	Milena Mihail , Christos Papadimitriou , Amin Saberi, On certain connectivity properties of the internet topology, Journal of Computer and System Sciences, v.72 n.2, p.239-251, March 2006
	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
	Colin Cooper , Alan Frieze, The cover time of the preferential attachment graph, Journal of Combinatorial Theory Series B, v.97 n.2, p.269-290, March, 2007
	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
	Benjamin Doerr , Tobias Friedrich , Thomas Sauerwald, Quasirandom rumor spreading, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.773-781, January 20-22, 2008, San Francisco, California
	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
	Chen Avin, Distance graphs: from random geometric graphs to Bernoulli graphs and between, Proceedings of the fifth international workshop on Foundations of mobile computing, August 18-21, 2008, Toronto, Canada