Constructing trees in parallel

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Constructing trees in parallel

Full text

Pdf (1.11 MB)

Source

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

Santa Fe, New Mexico, United States

Pages: 421 - 431

Year of Publication: 1989

ISBN:0-89791-323-X

Authors

M. J. Atallah	Department of Computer Science, Purdue University
S. R. Kosaraju	Department of Computer Science, Johns Hopkins University
L. L. Larmore	ICS, UC Irvine
G. L. Miller	School of Computer Science, CMU and Department of Computer Science
S.-H. Teng	School of Computer Science, CMU and Department of Computer Science

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGARCH: ACM Special Interest Group on Computer Architecture

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 10, Downloads (12 Months): 35, Citation Count: 7

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/72935.72980 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	[1] A. Apostolico, M. J. Atallah, L. L. Larmore and H. S. McFaddin. Efficient parallel algorithms for string editing and related problems. In Proc. 26th Annual Allerton Conf. on Communication, Control, and Computing, Monticello, Illinois, September 1988, pp. 253-263, 1988.
	2	[2] A. Aggarwal and J. Park. Notes on searching in multidimensional monotone arrays. In 29th Annual Symposium on Foundations of Computer Science, IEEE, 1988.
	3	Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
	4	[4] R. Cole. Parallel merge sort. In FOCS27, pages 511-516, IEEE, Toronto, October 1987.
	5	Shimon Even, Graph Algorithms, W. H. Freeman & Co., New York, NY, 1979
	6	[6] M. R. Garey Optimal binary search tree with restricted maximal depth. SIAM Journal of Computing , 3:101-110, 1974.
	7	[7] R. Guttler K. Mehlhorn and W. Schneider. Binary search trees: average and worst case behavior. Elektron. Informationsverarb Kybernet, 16:579-591, 1980.
	8	Richard W. Hamming, Coding and Information Theory, Prentice-Hall, Inc., Upper Saddle River, NJ, 1986
	9	[9] D. A. Huffman. A method for the construction of minimum redundancy codes. Proc. IRE, 40:1098- 1101, 1952.
	10	[10] D. E. Knuth. Optimal binary search trees. Acta Informatica, 1:14-25, 1971.
	11	Lawrence L. Larmore, Height restricted optimal binary trees, SIAM Journal on Computing, v.16 n.6, p.1115-1123, December 1, 1987 [doi>10.1137/0216070]
	12	Lawrence L. Larmore, A subquadratic algorithm for constructing approximately optimal binary search trees, Journal of Algorithms, v.8 n.4, p.579-591, December 1, 1987 [doi>10.1016/0196-6774(87)90052-6]
	13	[13] B. McMillan. Two inequalities implied by unique decipherability. IRE, Transaction on Information Theory, ():185-189, 1956.
	14	[14] G. L. Miller and J. H. Reif. Parallel tree contraction and its applications. In 26th Symposium on Foundations of Computer Science, pages 478-489, IEEE, Portland, Oregon, 1985.
	15	[15] G. L. Miller and S-H. Teng. Systematic methods for tree based parallel algorithm development. In Second International Conference on Supercomputing , pages 392-403, Santa Clara, May 1987.
	16	Victor Pan , John Reif, Fast and efficient parallel solution of sparse linear systems, SIAM Journal on Computing, v.22 n.6, p.1227-1250, Dec. 1993 [doi>10.1137/0222073]
	17	[17] W. L. Ruzzo. On uniform circuit complexity. Journal of Computer and System Sciences, 22(3):, June 1981.
	18	Shang-Hua Teng, The construction of Huffman-equivalent prefix code in NC, ACM SIGACT News, v.18 n.4, p.54-61, Summer 1987 [doi>10.1145/36068.36071]
	19	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 7

	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
	Marek Karpinski , Lawrence L. Larmore , Wojciech Rytter, Sequential and parallel subquadratic work algorithms for constructing approximately optimal binary search trees, Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms, p.36-41, January 28-30, 1996, Atlanta, Georgia, United States
	D. G. Kirkpatrick , T. Przytycka, Parallel construction of near optimal binary trees, Proceedings of the second annual ACM symposium on Parallel algorithms and architectures, p.234-243, July 02-06, 1990, Island of Crete, Greece
	Xin He , Zhi-Zhong Chen, Shortest path in complete bipartite digraph problem and its applications, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.230-238, January 05-07, 1997, New Orleans, Louisiana, United States
	Lawrence L. Larmore , Teresa M. Przytycka , Wojciech Rytter, Parallel construction of optimal alphabetic trees, Proceedings of the fifth annual ACM symposium on Parallel algorithms and architectures, p.214-223, June 30-July 02, 1993, Velen, Germany
	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
	Wolfgang W. Bein , Mordecai J. Golin , Lawrence L. Larmore , Yan Zhang, The Knuth-Yao quadrangle-inequality speedup is a consequence of total-monotonicity, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.31-40, January 22-26, 2006, Miami, Florida