Parallel searching in generalized Monge arrays with applications

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Parallel searching in generalized Monge arrays with applications

Full text

Pdf (1.14 MB)

Source

ACM Symposium on Parallel Algorithms and Architectures archive
Proceedings of the second annual ACM symposium on Parallel algorithms and architectures table of contents

Island of Crete, Greece

Pages: 259 - 268

Year of Publication: 1990

ISBN:0-89791-370-1

Authors

A. Aggarwal	IBM Research Division, T. J. Watson Research Center, Yorktown Heights, NY
D. Kravets	Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MA
J. Park	Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MA
S. Sen	Department of Computer Science, Duke University, Durham, NC

Sponsors

IEEE-CS : Computer Society
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGARCH: ACM Special Interest Group on Computer Architecture
CTI : Computer Technology Inst.
EATCS : European Association for Theoretical Computer Science
Computer Tech Inst. : Computer Technology Institute

Publisher

ACM New York, NY, USA

Bibliometrics

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

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

	AALM88	A. Apostoli~o, M. J. Atallah, L. L. Larmore, and H. S. McFaddin. Efficient parallel algorithms for string editing and related problems. In Proceedings of the 26ih A llerton Conference on Communication, Control~ and Computing, pages 253-263, October 1988.
	AK88	A. Aggarwal and M. M. Klawe. Applications of generalized matrix searching to geometric algorithms. Discrete Applied Mathematics, 1988. To appear. Presented at the Workshop on Computational Combinatorics, Simon Fraser University, August 1987.
	AKL+89	M. J. Atallah , S. R. Kosaraju , L. L. Larmore , G. L. Miller , S.-H. Teng, Constructing trees in parallel, Proceedings of the first annual ACM symposium on Parallel algorithms and architectures, p.421-431, June 18-21, 1989, Santa Fe, New Mexico, United States [doi>10.1145/72935.72980]
	AKM+87	A Aggarwal , M Klawe , S Moran , P Shor , R Wilber, Geometric applications of a matrix searching algorithm, Proceedings of the second annual symposium on Computational geometry, p.285-292, June 02-04, 1986, Yorktown Heights, New York, United States [doi>10.1145/10515.10546]
	AP89a	A. Aggarwal and J. Park. Parallel searching in multidimensional monotone arrays. Journal of Algorithms, 1989. Submitted. Portions of this paper appear in Proceedings of the 29th Annual IEEE Symposium on Foundations of Computer Science, pages 497-512, October 1988.
	AP89b	A. Aggarwal and J. Park. Sequential searching in multidimensional monotone arrays. Journal of Algorithms, 1989. Submitted. Portions of this paper appear in Proceedings of the 29th Annual IEEE Symposium on Foundations of Computer Science, pages 497-512, October 1988.
	AP89c	S. Aravind and C. Pandurangan. Efficient parallel algorithms for some rectangle problems. Unpublished manuscript. Department of Computer Science, Indian Institute of Technology, Madras, India, 1989.
	AP90	A. Aggarwal and J. Park. Improved algorithms for economic lot-size problems. Unpublished manuscript, 1990.
	AS87	A. Aggarwal , S. Suri, Fast algorithms for computing the largest empty rectangle, Proceedings of the third annual symposium on Computational geometry, p.278-290, June 08-10, 1987, Waterloo, Ontario, Canada [doi>10.1145/41958.41988]
	Ata89	M.J. Atallah. A faster parallel algorithm for a matrix searching problem. Technical report, Purdue University, 1989.
	BBG+89	O. Berkman , Z. Galil , B. Schieber , U. Vishkin, Highly parallelizable problems, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.309-319, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73036]
	Bre74	Richard P. Brent, The Parallel Evaluation of General Arithmetic Expressions, Journal of the ACM (JACM), v.21 n.2, p.201-206, April 1974 [doi>10.1145/321812.321815]
	EGGI90	David Eppstein , Zvi Galil , Raffaele Giancarlo , Giuseppe F. Italiano, Sparse dynamic programming, Proceedings of the first annual ACM-SIAM symposium on Discrete algorithms, p.513-522, January 22-24, 1990, San Francisco, California, United States
	Hof61	A.J. ttoffman. On simple transportation problems. In Convexity: Proceedings of Symposia in Pure Mathematics, Vol. 7, pages 317-327. American Mathematical Society, 1961.
	KK88	M.M. Klawe and D. J. Kleitman. An almost .linear time algorithm for generalized matrix searching. Technical Report ILl 6275, IBM Research Division, Almaden Research Center, August 1988.
	LLS89	F. T. Leighton, C. E. Leiserson, and E. Schwabe. Theory of parallel and vlsi computation: Lecture notes for 18.435/6.848. Research Seminar Series MIT/LCS/RSS 6, Massachusetts Institute of Technology, March 1989.
	LS89	Lawrence L. Larmore , Baruch Schieber, On-line dynamic programming with applications to the prediction of RNA secondary structure, Proceedings of the first annual ACM-SIAM symposium on Discrete algorithms, p.503-512, January 22-24, 1990, San Francisco, California, United States
	Mel89	R.C. Melville. An implementation technique for geometry algorithms. Unpublished manuscript. A. T. & T. Bell Laboratories, Murray Hill, NJ, 1989.
	Mon81	G. Monge. D~blai et remblai. M~moires de l'Acad~mie des Sciences, 1781.
	RS88	Sanjay Ranka , Sartaj Sahni, String editing on an SIMD hypercube multicomputer, Journal of Parallel and Distributed Computing, v.9 n.4, p.411-418, Aug. 1990 [doi>10.1016/0743-7315(90)90125-9]
	WF74	Robert A. Wagner , Michael J. Fischer, The String-to-String Correction Problem, Journal of the ACM (JACM), v.21 n.1, p.168-173, Jan. 1974 [doi>10.1145/321796.321811]
	Yao80	F. Frances Yao, Efficient dynamic programming using quadrangle inequalities, Proceedings of the twelfth annual ACM symposium on Theory of computing, p.429-435, April 28-30, 1980, Los Angeles, California, United States [doi>10.1145/800141.804691]

CITED BY 3

	Amitava Datta , Anil Maheshwari , Jörg-Rüdiger Sack, Optimal parallel algorithms for direct dominance problems, Nordic Journal of Computing, v.3 n.1, p.72-88, Spring 1996
	Pankaj K. Agarwal , Micha Sharir, Efficient algorithms for geometric optimization, ACM Computing Surveys (CSUR), v.30 n.4, p.412-458, Dec. 1998
	Dina Kravets , C. Greg Plaxton, All Nearest Smaller Values on the Hypercube, IEEE Transactions on Parallel and Distributed Systems, v.7 n.5, p.456-462, May 1996