Parallel construction of near optimal binary trees

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Parallel construction of near optimal binary trees

Full text

Pdf (844 KB)

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: 234 - 243

Year of Publication: 1990

ISBN:0-89791-370-1

Authors

D. G. Kirkpatrick	The University of British Columbia, Computer Science, Vancouver, B.C., Canada, V6T 1W5
T. Przytycka	The University of British Columbia, Computer Science, Vancouver, B.C., Canada, V6T 1W5

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): 4, Downloads (12 Months): 21, Citation Count: 1

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.97690 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.

	AKLMT89	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]
	BH85	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]
	C86	R.Cole, "Parallel merge sort", Proc 27th Annual IEEE Symp. on Foundation of Computer Science, 1986, 511-516.
	H73	T.C.Hu, "A new proof of the T-C algorithm", SIAM J.Appl. Math., Vol. 25, No 1, July 1973, 83-94.
	Huff52	D.A.Huffman, "A method for the construction of minimum redundancy codes", Proc. IRE, 40, 1952, 1098-1101.
	KP89	David G. Kirkpatrick , Teresa M Przytycka, Efficient Construction of Binary Trees with Almost Optimal Weighted Path Length, University of British Columbia, Vancouver, BC, Canada, 1989
	KR84	D.G.Kirkpatrick, S.Reisch, "Upper bound for sorting integers on random access machines", Theoretical Computer Science 28 (1984) 236-276.
	MRK88	Gary L. Miller , Vijaya Ramachandran , Erich Kaltofen, Efficient parallel evaluation of straight-line code and arithmetic circuits, SIAM Journal on Computing, v.17 n.4, p.687-695, August 1988 [doi>10.1137/0217044]
	M85	K.Mehlhorn, Data Structures and Algorithms 1: Sorting and Searching, Springer Verlag, (1984).
	T87	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]
	V75	L.Valiant, "Parallelism in comparison problems", SIAM J.Comput., vol. 4, 1975, 348-355.