Highly parallelizable problems

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Highly parallelizable problems

Full text

Pdf (1.17 MB)

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: 309 - 319

Year of Publication: 1989

ISBN:0-89791-307-8

Authors

O. Berkman	Department of Computer Science, Sackler Faculty of Exact Sciences, Tel Aviv University, Tel Aviv, Israel 69978 and Institute for Advanced Computer Studies, University of Maryland, College Park, Md
Z. Galil	Department of Computer Science, Sackler Faculty of Exact Sciences, Tel Aviv University, Tel Aviv, Israel 69978 and Department of Computer Science, Columbia University, New York, NY
B. Schieber	IBM Research Division, Thomas J. Watson Research, Center, P.O. Box 218, Yorktown Heights, NY
U. Vishkin	Department of Computer Science, Sackler Faculty of Exact Sciences, Tel Aviv University, Tel Aviv, Israel 69978 and Institute for Advanced Computer Studies, University of Maryland, College Park, Md and The Department of Computer Science, Courant Institute, New York University

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

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

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

	ACGOY-88	A. Aggarwal, B. Chazelle, L. Guiba~, C. O'Dunlaing and C. Yap, "Parallel computational geometry", Algorithmica, 8 (1988), pp. 203-327.
	AG-86	Mikhail J. Atallah , Michael T. Goodrich, Efficient parallel solutions to some geometric problems, Journal of Parallel and Distributed Computing, v.3 n.4, p.492-507, December 1, 1986 [doi>10.1016/0743-7315(86)90011-0]
	AS-87	N. Alon and B. Schieber, "Optimal preprocessing for answering on-line product queries", TR 71/87, The Moise and Frida Eskena~y Institute of Computer Science, Tel Aviv University (1987).
	BG-88	D. Breslauer and Z. Galil, "An optimal O (loglogn) time parallel string matching algorithm", manuscript, 1988.
	BHa-87	P. Beame , J. Hastad, Optimal bounds for decision problems on the CRCW PRAM, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.83-93, January 1987, New York, New York, United States [doi>10.1145/28395.28405]
	BHo-85	A. Borodin , J. E. Hopcroft, Routing, merging, and sorting on parallel models of computation, Journal of Computer and System Sciences, v.30 n.1, p.130-145, Feb. 1985 [doi>10.1016/0022-0000(85)90008-X]
	BLSZ-87	H. A. Burgdorff , S. Jajodia , F. N. Springsteel , Y. Zalcstein, Alternative methods for the reconstruction of trees from their traversals, BIT, v.27 n.2, p.134-140, 1987
	BSV-88	O. Berkman, B. Schieber and U. Vishkin, "Some doubly logarithmic parallel algorithms based on finding all nearest smaller values", UMIACS-TR-88-79, University of Maryland Inst. for Advanced Comp. Studies (1988).
	BV-85	Ilan Bar-on , Uzi Vishkin, Optimal parallel generation of a computation tree form, ACM Transactions on Programming Languages and Systems (TOPLAS), v.7 n.2, p.348-357, April 1985 [doi>10.1145/3318.3478]
	BeV-89	O. Berkman and U. Vishkin, "Fully and almost fully parallel algorithmic techniques'', manuscript, January 1989.
	CDR-86	Stephen Cook , Cynthia Dwork , Ru&duml;ger Reischuk, Upper and lower time bounds for parallel random access machines without simultaneous writes, SIAM Journal on Computing, v.15 n.1, p.87-97, Feb. 1986 [doi>10.1137/0215006]
	CV-86	Richard Cole , Uzi Vishkin, Deterministic coin tossing with applications to optimal parallel list ranking, Information and Control, v.70 n.1, p.32-53, July 1986 [doi>10.1016/S0019-9958(86)80023-7]
	CYL-88	Gen-Huey Chen , M. S. Yu , L. T. Liu, Two algorithms for constructing a binary tree from its traversals, Information Processing Letters, v.28 n.6, p.297-299, Aug. 29, 1988 [doi>10.1016/0020-0190(88)90177-9]
	DS-83	Eliezer Dekel , Sartaj Sahni, Parallel Generation of Postfix and Tree Forms, ACM Transactions on Programming Languages and Systems (TOPLAS), v.5 n.3, p.300-317, July 1983 [doi>10.1145/2166.357211]
	FMW-87	F.E. Fich, F. Meyer auf der Heide and A. Wigderson, "Lower bounds for parallel random access machines with unbounded shared memory", Advances in Computer Research, 4 (1987), 1-15.
	FRW-88	Faith E. Fich , Prabhakar Ragde , Avi Wigderson, Relations between concurrent-write models of parallel computation, SIAM Journal on Computing, v.17 n.3, p.606-627, June 1988 [doi>10.1137/0217037]
	Ga-85	Zvi Galil, Optimal parallel algorithms for string matching, Information and Control, v.67 n.1-3, p.144-157, Oct./Nov./Dec. 1986 [doi>10.1016/S0019-9958(85)80031-0]
	Go-87a	M.T. Goodrich, "Triangulating a polygon in parallel", preprint, 1987.
	Go-87b	M. T. Goodrich, Finding the convex hull of a sorted point set in parallel, Information Processing Letters, v.26 n.4, p.173-179, Dec. 4, 1987 [doi>10.1016/0020-0190(87)90002-0]
	Go-87c	Michael Truman Goodrich , Mikhail J. Atallah, Efficient parallel techniques for computational geometry, 1987
	GBT-84	Harold N. Gabow , Jon Louis Bentley , Robert E. Tarjan, Scaling and related techniques for geometry problems, Proceedings of the sixteenth annual ACM symposium on Theory of computing, p.135-143, December 1984 [doi>10.1145/800057.808675]
	HH-82	R. Haggkvist and P. Hell, "Sorting and merging in rounds", SIAM J. on Alg. and Disc. Methods, 3 (1982), pp. 465-473.
	Kr-83	C.P. Kruskal, "Searching, merging, and sorting in parallel computation", ~EEE Trans. on Computers, C-32 (1983), pp. 942-046.
	KLP-88	Z.M. Kedem, G.M. Landau and K.V. Palem, "Optimal parallel algorithms for matching problems", TR 410, Dept. of Computer Science, Courant inst., NYU (1988).
	LF-80	Richard E. Ladner , Michael J. Fischer, Parallel Prefix Computation, Journal of the ACM (JACM), v.27 n.4, p.831-838, Oct. 1980 [doi>10.1145/322217.322232]
	MW-85	F. Meyer auf der Heide and A. Wigderson, "The complexity of parallel sorting", Proe. 26th Syrup. on Foundations of Computer Science (1985), pp. 532-540.
	RV-88	V. Ramachandran , U. Vishkin, Efficient parallel triconnectivity in logarithmic time (extended abstract), VLSI Algorithms and Architectures, Springer-Verlag, London, 1988
	Sc-87	B. Schieber, "Design and analysis of some parallel algorithms", Ph.D. thesis, Dept. of Computer Science, Tel Aviv Univ., 1987.
	SV-81	Y. Shiloach and U. Vishkin, "Finding the maximum, merging and sorting in a parallel computation model", J. of Algorithms, 2 (1981), pp. 88-102.
	ScV-88	B. Schieber , U. Vishkin, Finding all nearest neighbors for convex polygons in parallel: a new lower bound technique and a matching algorithm, Discrete Applied Mathematics, v.29 n.1, p.97-111, Nov. 1990 [doi>10.1016/0166-218X(90)90084-P]
	Va-75	L.G. Valiant, "Parallelism in comparison models", SIAM or. on Computing, 4 (1975), pp. 348-355.
	Vi-85	Uzi Vishkin, Optimal parallel pattern matching in strings, Information and Control, v.67 n.1-3, p.91-113, Oct./Nov./Dec. 1986 [doi>10.1016/S0019-9958(85)80028-0]
	Vu-80	Jean Vuillemin, A unifying look at data structures, Communications of the ACM, v.23 n.4, p.229-239, April 1980 [doi>10.1145/358841.358852]
	Ya-82	Andrew C. Yao, Space-time tradeoff for answering range queries (Extended Abstract), Proceedings of the fourteenth annual ACM symposium on Theory of computing, p.128-136, May 05-07, 1982, San Francisco, California, United States [doi>10.1145/800070.802185]

CITED BY 15

	Philip D. MacKenzie , Quentin F. Stout, Ultra-fast expected time parallel algorithms, Proceedings of the second annual ACM-SIAM symposium on Discrete algorithms, p.414-423, January 28-30, 1991, San Francisco, California, United States
	Lawrence L. Larmore , Teresa M. Przytycka, Parallel construction of trees with optimal weighted path length, Proceedings of the third annual ACM symposium on Parallel algorithms and architectures, p.71-80, July 21-24, 1991, Hilton Head, South Carolina, United States
	A. Aggarwal , D. Kravets , J. Park , S. Sen, Parallel searching in generalized Monge arrays with applications, Proceedings of the second annual ACM symposium on Parallel algorithms and architectures, p.259-268, July 02-06, 1990, Island of Crete, Greece
	Mujtaba R. Ghouse , Michael T. Goodrich, In-place techniques for parallel convex hull algorithms (preliminary version), Proceedings of the third annual ACM symposium on Parallel algorithms and architectures, p.192-203, July 21-24, 1991, Hilton Head, South Carolina, United States
	Michael T. Goodrich , Yossi Matias , Uzi Vishkin, Optimal parallel approximation for prefix sums and integer sorting, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.241-250, January 23-25, 1994, Arlington, Virginia, United States
	Amihood Amir , Moshe Lewenstein , Ely Porat, Faster algorithms for string matching with k mismatches, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.794-803, January 09-11, 2000, San Francisco, California, United States
	U. Vishkin, Deterministic sampling—a new technique for fast pattern matching, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.170-180, May 13-17, 1990, Baltimore, Maryland, United States
	Danny Z. Chen, Efficient Geometric Algorithms on the EREW PRAM, IEEE Transactions on Parallel and Distributed Systems, v.6 n.1, p.41-47, January 1995
	Martin Farach , S. Muthukrishnan, Optimal parallel dictionary matching and compression (extended abstract), Proceedings of the seventh annual ACM symposium on Parallel algorithms and architectures, p.244-253, June 24-26, 1995, Santa Barbara, California, United States
	Amihood Amir , Moshe Lewenstein , Ely Porat, Faster algorithms for string matching with k mismatches, Journal of Algorithms, v.50 n.2, p.257-275, February 2004
	Dharmavani Bhagavathi , Venkata V. Bokka , Himabindu Gurla , Stephan Olariu , James L. Schwing , Ivan Stojmenovic , Jingyuan Zhang, Time-Optimal Visibility-Related Algorithms on Meshes with Multiple Broadcasting, IEEE Transactions on Parallel and Distributed Systems, v.6 n.7, p.687-703, July 1995
	R. A. Baeza-Yates, Algorithms for string searching, ACM SIGIR Forum, v.23 n.3-4, p.34-58, Spring 1989
	Amihood Amir , Gad M. Landau , Usi Vishkin, Efficient pattern matching with scaling, Proceedings of the first annual ACM-SIAM symposium on Discrete algorithms, p.344-357, January 22-24, 1990, San Francisco, California, United States
	Danny Krizanc , Pat Morin , Michiel Smid, Range mode and range median queries on lists and trees, Nordic Journal of Computing, v.12 n.1, p.1-17, March 2005
	Z. M. Kedem , G. M. Landau , K. V. Palem, Optimal parallel suffix-prefix matching algorithm and applications, Proceedings of the first annual ACM symposium on Parallel algorithms and architectures, p.388-398, June 18-21, 1989, Santa Fe, New Mexico, United States