Trading space for time in undirected s-t connectivity

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Trading space for time in undirected s-t connectivity

Full text

Pdf (711 KB)

Source

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

Seattle, Washington, United States

Pages: 543 - 549

Year of Publication: 1989

ISBN:0-89791-307-8

Authors

A. Z. Broder	DEC Systems Research Center, Palo Alto, CA
A. R. Karlin	DEC Systems Research Center, Palo Alto, CA
P. Raghavan	IBM T.J. Watson Research Center, Yorktown Heights, NY
E. Upfal	BIBM Almaden Research Center, San Jose, CA

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 0, Downloads (12 Months): 12, Citation Count: 7

Additional Information:

abstract 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/73007.73059 What is a DOI?

ABSTRACT

Aleliunas et al. [1] posed the following question: “The reachability problem for undirected graphs can be solved in logspace and O(mn) time [m is the number of edges and n is the number of vertices] by a probabilistic algorithm that simulates a random walk, or in linear time and space by a conventional deterministic graph traversal algorithm. Is there a spectrum of time-space trade-offs between these extremes?” We answer this question in the affirmative for linear-sized graphs by presenting an algorithm which is faster than the random walk by a factor essentially proportional to the size of its workspace. For denser graphs, the algorithm is faster than the random walk but the speed-up factor is smaller.

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'gsz, and C. l~ackoff. Random walks, universal traversal sequences, and the complexity of maze problems. In 20th Annual Symposium on Foundations of Computer Science, pages 218-223, San Juan, Puerto Rico, October 1979.
	2	P. Beame, A. Borodin, P. Raghavan, W.L. l~uzzo, and M. Tompa. 1988. Private Communication.
	3	A. Borodin , S. A. Cook , P. W. Dymond , W. L. Ruzzo , M. Tompa, Two applications of inductive counting for complementation problems, SIAM Journal on Computing, v.18 n.3, p.559-578, June 1989 [doi>10.1137/0218038]
	4	T.K. Carne. A transmutation formula for markov chains. Bull. Sc. Math., 2~ sgrie, 109:399-405, 1985.
	5	S. A. Cook and C. W. Rackoff. Space lower bounds for maze threadability on restricted machines. SIAM Journal on Computing, 9(3):636-652, 1980.
	6	Michael L. Fredman , János Komlós , Endre Szemerédi, Storing a Sparse Table with 0(1) Worst Case Access Time, Journal of the ACM (JACM), v.31 n.3, p.538-544, July 1984 [doi>10.1145/828.1884]
	7	Anna R. Karlin , Eli Upfal, Parallel hashing: an efficient implementation of shared memory, Journal of the ACM (JACM), v.35 n.4, p.876-892, Oct. 1988 [doi>10.1145/48014.350550]
	8	H. R. Lewis and C. H. Papadimitriou. Symmetric space-bounded computation. Theoretical Computer Science, 19:161-187, 1982.

CITED BY 7

	J. Ullman , M. Yannakakis, High-probability parallel transitive closure algorithms, Proceedings of the second annual ACM symposium on Parallel algorithms and architectures, p.200-209, July 02-06, 1990, Island of Crete, Greece
	Jeff Edmonds, Time-space trade-offs for undirected st-connectivity on a JAG, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.718-727, May 16-18, 1993, San Diego, California, United States
	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
	Greg Barnes , Walter L. Ruzzo, Deterministic algorithms for undirected s-t connectivity using polynomial time and sublinear space., Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.43-53, May 05-08, 1991, New Orleans, Louisiana, United States
	A. Borodin , W. L. Ruzzo , M. Tompa, Lower bounds on the length of universal traversal sequences, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.562-573, May 14-17, 1989, Seattle, Washington, United States
	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
	M. Bakhouya , J. Gaber , A. Koukam, Distributed holonic multi-agent system for resource discovery in grids, Multiagent and Grid Systems, v.2 n.1, p.1-9, January 2006