On the Optimality of Some Set Algorithms

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

On the Optimality of Some Set Algorithms

Full text

Pdf (668 KB)

Source

Journal of the ACM (JACM) archive
Volume 19 , Issue 4 (October 1972) table of contents

Pages: 649 - 659

Year of Publication: 1972

ISSN:0004-5411

Author

Edward M. Reingold

University of Illinois at Urbana-Champaign, Department of Computer Science, Urbana, IL

Publisher

ACM New York, NY, USA

Bibliometrics

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

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/321724.321730 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	Manuel Blum , Robert W. Floyd , Vaughan Pratt , Ronald L. Rivest , Robert E. Tarjan, Linear time bounds for median computations, Proceedings of the fourth annual ACM symposium on Theory of computing, p.119-124, May 01-03, 1972, Denver, Colorado, United States [doi>10.1145/800152.804904]
	2	FORD, L. R. JR., AND JOHNSON, S. M. A tournament problem. Amer. Math. Mon. 66 (1959), 387-389.
	3	Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998
	4	RABIN, M.O. Proving simultaneous positivity of linear forms. Presented at Third Annual ACM Symp. on Theory of Computing, Shaker Heights, Ohio, 1971 (unpublished).
	5	STEINHAUS, H. Mathematical Snapshots. Oxford U. Press, New York, 1st ed., 1950; 2nd ed., 1960.
	6	STEINHAUS, H. Some remarks about tournaments. Calcutta Math. Soc., Golden Jubilee Commem. Vol. (1958-1959), Pt. II, pp. 323-327.

CITED BY 13

	Donald B. Johnson , Samuel D. Kashdan, Lower Bounds for Selection in X + Y and Other Multisets, Journal of the ACM (JACM), v.25 n.4, p.556-570, Oct. 1978
	J. D. Ullman , A. V. Aho , D. S. Hirschberg, Bounds on the Complexity of the Longest Common Subsequence Problem, Journal of the ACM (JACM), v.23 n.1, p.1-12, Jan. 1976
	Bing-Chao Huang , Michael A. Langston, Stable set and multiset operations in optimal time and space, Proceedings of the seventh ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.288-293, March 1988, Austin, Texas, United States
	Udi Manber , Martin Tompa, Probabilistic, nondeterministic, and alternating decision trees (Preliminary Version), Proceedings of the fourteenth annual ACM symposium on Theory of computing, p.234-244, May 05-07, 1982, San Francisco, California, United States
	Bruce Weide, A Survey of Analysis Techniques for Discrete Algorithms, ACM Computing Surveys (CSUR), v.9 n.4, p.291-313, Dec. 1977
	Shlomo Moran , Marc Snir , Udi Manber, Applications of Ramsey's theorem to decision tree complexity, Journal of the ACM (JACM), v.32 n.4, p.938-949, Oct. 1985
	Frank Fussenegger , Harold N. Gabow, A Counting Approach to Lower Bounds for Selection Problems, Journal of the ACM (JACM), v.26 n.2, p.227-238, April 1979
	Michael Ben-Or, Lower bounds for algebraic computation trees, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.80-86, December 1983
	Bernard M. E. Moret, Decision Trees and Diagrams, ACM Computing Surveys (CSUR), v.14 n.4, p.593-623, Dec. 1982
	Udi Manber , Martin Tompa, The complexity of problems on probabilistic, nondeterministic, and alternating decision trees, Journal of the ACM (JACM), v.32 n.3, p.720-732, July 1985
	Friedhelm Meyer auf der Heide, Fast algorithms for N-dimensional restrictions of hard problems, Journal of the ACM (JACM), v.35 n.3, p.740-747, July 1988
	Nir Halman, A linear time algorithm for the weighted lexicographic rectilinear 1-center problem in the plane, Information Processing Letters, v.86 n.3, p.121-128, 16 May 2003
	Kumar Vadaparty , Shamim Naqvi, Using Constraints for Efficient Query Processing in Nondeterministic Databases, IEEE Transactions on Knowledge and Data Engineering, v.7 n.6, p.850-864, December 1995