Deterministic algorithms for undirected s-t connectivity using polynomial time and sublinear space.

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Deterministic algorithms for undirected s-t connectivity using polynomial time and sublinear space.

Full text

Pdf (1.10 MB)

Source

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

New Orleans, Louisiana, United States

Pages: 43 - 53

Year of Publication: 1991

ISBN:0-89791-397-3

Authors

Greg Barnes	Univ. of Washington, Seattle
Walter L. Ruzzo	Univ. of Washington, Seattle

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 2, Downloads (12 Months): 15, Citation Count: 2

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/103418.103430 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.

	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. In 20th Annual Symposium on Foundations of Computer Science, pages 218-223, San Juan, Puerto Rico, Oct. 1979. IEEE.
	2	N. Alon , Y. Azar , Y. Ravid, Universal sequences for complete graphs, Discrete Applied Mathematics, v.27 n.1-2, p.25-28, May 1990 [doi>10.1016/0166-218X(90)90125-V]
	3	L. Babai , N. Nisan, Multiparty protocols and logspace-hard pseudorandom sequences, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.1-11, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73008]
	4	Amotz Bar-Noy , Allen Borodin , Mauricio Karchmer , Nathan Linial , Michael Werman, Bounds on universal sequences, SIAM Journal on Computing, v.18 n.2, p.268-277, April 1989 [doi>10.1137/0218018]
	5	P. Beame, A. Borodin, P. l#aghavan, W. L. Ruzzo, and M. Tompa. Time-space tradeoffs for undirected graph connectivity. In 31st Annual Symposium on Foundations of Computer Science, pages 429-438, St. Louis, M 0, Oct. 1990. IEEE.
	6	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]
	7	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 [doi>10.1145/73007.73061]
	8	Michael F. Bridgland, Universal traversal sequences for paths and cycles, Journal of Algorithms, v.8 n.5, p.395-404, Sept. 1987 [doi>10.1016/0196-6774(87)90019-8]
	9	A. Z. Broder , A. R. Karlin , P. Raghavan , E. Upfal, Trading space for time in undirected s-t connectivity, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.543-549, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73059]
	10	S. A. Cook and C. W. Rackoff. Space lower bounds for maze threadability on restricted machines. SIAM Journal on Computing, 9(3):636-652, Aug. 1980.
	11	S. Hoory and A. Wigderson. Universal sequences for expander graphs. Hebrew University, Jerusalem, Dec. 1989.
	12	Sorin Istrail, Polynomial universal traversing sequences for cycles are constructible, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.491-503, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62260]
	13	S. Istrail. Constructing generalized universal traversing sequences of polynomial size for graphs with small diameter. In 31st Annual Symposium on Foundations of Computer Science, pages 439-448, St. Louis, MO, Oct. 1990. IEEE.
	14	Howard J. Karloff , Ramamohan Paturi , Janos Simon, Universal traversal sequences of length nO(log n) for cliques, Information Processing Letters, v.28 n.5, p.241-243, Aug. 12, 1988 [doi>10.1016/0020-0190(88)90197-4]
	15	Donald E. Knuth, The Art of Computer Programming Volumes 1-3 Boxed Set, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1998
	16	K Kriegel, The space complexity of the accessibility problem for undirected graphs of log n bounded genus, Proceedings of the 12th symposium on Mathematical foundations of computer science 1986, p.484-492, June 1986, Bratislava, Czechoslovakia
	17	H. R. Lewis and C. H. Papadimitriou. Symmetric space-bounded computation. Theoretical Computer Science, 19"161-187, 1982.
	18	N. Nisan, Pseudorandom generators for space-bounded computations, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.204-212, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100242]
	19	N. Pippenger. Pebbling. In Proceedings of the Fifth IBM Symposium on Mathematical Foundations of Computer Science. IBM Japan, May 1980.
	20	W. J. Savitch. Relationships between nondeterministic and deterministic tape complexities. Journal of Computer and System Sciences, 4(2)'177-192, 1970.
	21	Robert Endre Tarjan, Efficiency of a Good But Not Linear Set Union Algorithm, Journal of the ACM (JACM), v.22 n.2, p.215-225, April 1975 [doi>10.1145/321879.321884]
	22	M. Tompa. Two familiar transitive closure algorithms which admit no polynomial time, sublinear space implementations. SIAM Journal on Computing, I1(1):130-137, Feb. 1982.
	23	M. Tompa. Lower bounds on universal traversal sequences for cycles and higher degree graphs. Technical Report 90-07-02, University of Washington, Department of Computer Science and Engineering, July 1990.
	24	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 [doi>10.1145/97444.97686]

CITED BY 2

	David R. Karger , Noam Nisan , Michal Parnas, Fast connected components algorithms for the EREW PRAM, Proceedings of the fourth annual ACM symposium on Parallel algorithms and architectures, p.373-381, June 29-July 01, 1992, San Diego, California, United States
	Noam Nisan, RL⊆SC, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.619-623, May 04-06, 1992, Victoria, British Columbia, Canada