Lower bounds for the union-find and the split-find problem on pointer machines

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Lower bounds for the union-find and the split-find problem on pointer machines

Full text

Pdf (1.04 MB)

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: 34 - 44

Year of Publication: 1990

ISBN:0-89791-361-2

Author

J. A. La Poutré

Department of Computer Science, Utrecht University, P.O. Box 80.089, 3508 TB Utrecht, The Netherlands

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

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

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.100221 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	L. Banachowsky, A Complement to Tarjan's Result about the Lower Bound on the Complexity of the Set Union Problem, Inf. Process. Lett. 11 (1980), 59-65.
	2	Norbert Blum, On the single-operation worst-case time complexity of the disjoint set union problem, SIAM Journal on Computing, v.15 n.4, p.1021-1024, Nov. 1986 [doi>10.1137/0215072]
	3	P. v. Erode Boas, R. Kaas and E. Zijlstra, Design and Implementation of an Efficient Priority Queue, Math. Systems Theory 10 (1977), 99-127.
	4	M. Fredman , M. Saks, The cell probe complexity of dynamic data structures, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.345-354, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73040]
	5	H.N Gabow, A Scaling Algorithm for Weighted Matching on General Graphs, Proc. 26 th Ann. Syrup. on Found. of Comp. Sci. (FOCS) 1985, 90-100.
	6	H.N. Gabow and R.E. Tarjan, A Linear-Time Algorithm for a Special Case of Disjoint Set Union, J. Comput. Syst. Sci., no. 30, 1985, pp. 209-221.
	7	Donald E. Knuth, The art of computer programming, volume 1 (3rd ed.): fundamental algorithms, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1997
	8	A.N. Kolmogorov, On the Notion of Algorithms, Uspekhi Mat. Nauk., 8 (1953), 175-176.
	9	J. A. La Poutré, New techniques for the union-find problem, Proceedings of the first annual ACM-SIAM symposium on Discrete algorithms, p.54-63, January 22-24, 1990, San Francisco, California, United States
	10	J.A. La Poutrt, A Fast and Optimal Algorithm for the Split- Find Problem on Pointer Machines, Tech. Rep. RUU-CS- 89-20, Utrecht University, 1989.
	11	J.A. La Poutrt, Lower Bounds for the Union-Find and the Split-Find Problem on Pointer Machines, Tech. Rep. RUU- CS-89-21, Utrecht University, 1989
	12	Kurt Mehlhorn , Stefan Näher , Helmut Alt, A lower bound on the complexity of the union-split-find problem, SIAM Journal on Computing, v.17 n.6, p.1093-1102, Dec. 1988 [doi>10.1137/0217070]
	13	A. Schonhage, Storage Modification Machines, SIAM J. Comput. 9 (1980), 490-508.
	14	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]
	15	R.E. Tarjan, A Class of Algorithms which Require Nonlinear Time to Maintain Disjoint Sets, J. Comput. Syst. Sci. 18 (1979), 110-127.
	16	Robert E. Tarjan , Jan van Leeuwen, Worst-case Analysis of Set Union Algorithms, Journal of the ACM (JACM), v.31 n.2, p.245-281, April 1984 [doi>10.1145/62.2160]

CITED BY 5

	Peter Bro Miltersen, Lower bounds for union-split-find related problems on random access machines, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.625-634, May 23-25, 1994, Montreal, Quebec, Canada
	Johannes A. La Poutré, Alpha-algorithms for incremental planarity testing (preliminary version), Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.706-715, May 23-25, 1994, Montreal, Quebec, Canada
	Marc J. van Kreveld , Mark H. Overmars, Union-copy structures and dynamic segment trees, Journal of the ACM (JACM), v.40 n.3, p.635-652, July 1993
	Paul Beame , Faith E. Fich, Optimal bounds for the predecessor problem and related problems, Journal of Computer and System Sciences, v.65 n.1, p.38-72, August 2002
	Zvi Galil , Giuseppe F. Italiano, Data structures and algorithms for disjoint set union problems, ACM Computing Surveys (CSUR), v.23 n.3, p.319-344, Sept. 1991

INDEX TERMS

Primary Classification:
E. Data

Additional Classification:
F. Theory of Computation
F.1 COMPUTATION BY ABSTRACT DEVICES
F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
F.2.2 Nonnumerical Algorithms and Problems
Subjects: Computations on discrete structures

General Terms:
Algorithms

Collaborative Colleagues:

J. A. La Poutré: colleagues

Adobe Acrobat

QuickTime

Windows Media Player

Real Player