Parallel construction of trees with optimal weighted path length

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Parallel construction of trees with optimal weighted path length

Full text

Pdf (771 KB)

Source

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

Hilton Head, South Carolina, United States

Pages: 71 - 80

Year of Publication: 1991

ISBN:0-89791-438-4

Authors

Lawrence L. Larmore	Department of Computer Science, University of California, Riverside, CA
Teresa M. Przytycka	Department of Computer Science, University of California, Riverside, CA and Instytut Informatyki, Uniwersytet Warszawski

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): 2, Downloads (12 Months): 12, Citation Count: 3

Additional Information:

references cited by index terms collaborative colleagues peer to peer

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/113379.113386 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	K. Abrahamson , N. Dadoun , D. G. Kirkpatrick , T. Przytycka, A simple parallel tree contraction algorithm, Journal of Algorithms, v.10 n.2, p.287-302, June 1989 [doi>10.1016/0196-6774(89)90017-5]
	2	Alberto Apostolico , Mikhail J. Atallah , Lawrence L. Larmore , Scott McFaddin, Efficient parallel algorithms for string editing and related problems, SIAM Journal on Computing, v.19 n.5, p.968-988, Oct. 1990 [doi>10.1137/0219066]
	3	A.Aggarwal, J.Park. Notes on searching in multidimensional monotone arrays. In ~gth Annual Symposium on Foundation of Computer Science IEEE (1988).
	4	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]
	5	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]
	6	Kwong-fai Chan , Tak-wah Lam, Finding least-weight subsequences with fewer processors, Proceedings of the international symposium on Algorithms, p.318-327, August 1990, Tokyo, Japan
	7	Z. Galil and R. Giancarlo. Data Structures and Algorithms for Approximate String Matching, Tech. Report, CS Dept., Columbia University, NY (1987).
	8	M.C. Golumbic. Combinatorial Merging, IEEE Trans. Comp. 25, 11 (1976) 1164-1167.
	9	R. Grittier, K. Mehlhorn and W. Schneider. Binary search trees: average and worst case behavior, Electron. Informationsverarb Kybernet, 16 (1980) pp. 41- 61.
	10	D. S. Hirschberg , L. L. Larmore, The least weight subsequence problem, SIAM Journal on Computing, v.16 n.4, p.628-638, Aug. 1987 [doi>10.1137/0216043]
	11	T.C. Hu and K.C. Tan. Path length of binary search trees, SIAM J. Appl. Math. 22, pp. 225-234 (1972).
	12	T.C.Hu and C.Tucker. Optimum computer search trees. SIAM J.Appl. Math., 21, 1971, pp 514-532.
	13	D.A. Huffman. A method for the constructing of minimum redundancy codes, Proc. IRE, 40, 1952, 1098-1101.
	14	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 [doi>10.1145/97444.97690]
	15	D.G.Kirkpatrick and T.M.Przytycka. An optimal parallel minimax tree algorithm, Proc. of the 2nd IEEE Symp. of Parallel and Distributed Processing (1990) 293-300.
	16	M.M. Klawe and D.J. Kleitman, An almost linear time algorithm for generalized matrix searching, RJ 6275, IBM- Research Division, Almaden Research Center, (1988)
	17	L.L. Larmore. Length limited coding and optimal height-limited binary trees, TR 88-01 University of California, Irvine (1988).
	18	Lawrence L. Larmore , Daniel S. Hirschberg, A fast algorithm for optimal length-limited Huffman codes, Journal of the ACM (JACM), v.37 n.3, p.464-473, July 1990 [doi>10.1145/79147.79150]
	19	Lawrence L. Larmore , Daniel S. Hirschberg, Length-limited coding, Proceedings of the first annual ACM-SIAM symposium on Discrete algorithms, p.310-318, January 22-24, 1990, San Francisco, California, United States
	20	L.L.Larmore, and T.M.Przytycka, A Fast Algorithm for Optimum Height Limited Alphabetic Binary Trees, manuscript.
	21	G.L. Miller and J. Reif. Parallel tree contraction and its appfication, Proc. 26th IEEE Syrup. on Foundation of Computer Science (1985) pp. 478-489.
	22	Teresa Maria Przytycka, Parallel techniques for construction of trees and related problems, University of British Columbia, Vancouver, BC, Canada, 1992
	23	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]
	24	Robert Wilber, The concave least-weight subsequence problem revisited, Journal of Algorithms, v.9 n.3, p.418-425, September 1988 [doi>10.1016/0196-6774(88)90032-6]
	25	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

	Baruch Schieber, Computing a minimum-weight k-link path in graphs with the concave Monge property, Proceedings of the sixth annual ACM-SIAM symposium on Discrete algorithms, p.405-411, January 22-24, 1995, San Francisco, California, 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
	Alok Aggarwal , Baruch Schieber , Takashi Tokuyama, Finding a minimum weight K-link path in graphs with Monge property and applications, Proceedings of the ninth annual symposium on Computational geometry, p.189-197, May 18-21, 1993, San Diego, California, United States