A Shifting Algorithm for Min-Max Tree Partitioning

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A Shifting Algorithm for Min-Max Tree Partitioning

Full text

Pdf (486 KB)

Source

Journal of the ACM (JACM) archive
Volume 29 , Issue 1 (January 1982) table of contents

Pages: 58 - 67

Year of Publication: 1982

ISSN:0004-5411

Authors

Ronald I. Becker	Department of Mathematics, University of Cape Town, 7700 Rondebosch, South Africa
Stephen R. Schach	Department of Computer Science, University of Cape Town, 7700 Rondebosch, South Africa
Yehoshua Perl	Mathematics and Computer Science, Bar-Ilan University, RamatGan, Isreal

Publisher

ACM New York, NY, USA

Bibliometrics

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

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/322290.322294 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	BECKER, R I, PERL, Y., A~D SCHACH, S.R An effioent implementation of an algorithm for mmmax tree partmonmg. Res Rep, Mathemaucs Dep, Umv of Cape Town, South Africa, 1980
	2	HADLOCK, F Minimum spanning forests of bounded trees Proc. 5th Southeast Conf on Comb,- natoncs, Graph Theory, and Comput,ng, Boca Raton, Fla, 1974, pp 449-460
	3	HARARY, F Graph Theory Addison-Wesley, Reading, Mass, 1969, Ch 4.
	4	KARIV, O, AND HAKIMI, S L An algorithmic approach to network locauon problems Part 1' The pcentres SIAM. J AppI Math 37, 3 (1979), 513-538
	5	KARIV, O, AND HAKIMI, S L An algor,thmtc approach to network locauon problems Part 2 The pmedians SIAM J Appl Math. 37, 3 (1979), 539-560
	6	KUNDU, S, AND MISRA, J. A hnear tree pamt,onlng algorithm SlAM J Compuong 6, 1 (1977), 151-154
	7	Yehoshua Perl , Stephen R. Schach, Max-Min Tree Partitioning, Journal of the ACM (JACM), v.28 n.1, p.5-15, Jan. 1981 [doi>10.1145/322234.322236]

CITED BY 10

	Ronald Becker , Bruno Simeone , Yen-I Chiang, A shifting algorithm for continuous tree partitioning, Theoretical Computer Science, v.282 n.2, p.353-380, 10 June 2002
	Yehoshua Perl , Stephen R. Schach, Max-Min Tree Partitioning, Journal of the ACM (JACM), v.28 n.1, p.5-15, Jan. 1981
	Nimrod Megiddo, Applying Parallel Computation Algorithms in the Design of Serial Algorithms, Journal of the ACM (JACM), v.30 n.4, p.852-865, Oct. 1983
	Frank Dehne , Todd Eavis , Andrew Rau-Chaplin, The cgmCUBE project: Optimizing parallel data cube generation for ROLAP, Distributed and Parallel Databases, v.19 n.1, p.29-62, January 2006
	Frank Dehne , Todd Eavis , Susanne Hambrusch , Andrew Rau-Chaplin, Parallelizing the Data Cube, Distributed and Parallel Databases, v.11 n.2, p.181-201, March 2002
	Greg N. Frederickson, Optimal algorithms for tree partitioning, Proceedings of the second annual ACM-SIAM symposium on Discrete algorithms, p.168-177, January 28-30, 1991, San Francisco, California, United States
	Nir Halman , Arie Tamir, Continuous bottleneck tree partitioning problems, Discrete Applied Mathematics, v.140 n.1-3, p.185-206, 15 May 2004
	Roberto Cordone, A subexponential algorithm for the coloured tree partition problem, Discrete Applied Mathematics, v.155 n.10, p.1326-1335, May, 2007
	Bang Ye Wu , Hung-Lung Wang , Shih Ta Kuan , Kun-Mao Chao, On the uniform edge-partition of a tree, Discrete Applied Mathematics, v.155 n.10, p.1213-1223, May, 2007
	Yan Chen , Yehoshua Perl , James Geller , George Hripcsak , Li Zhang, Comparing and consolidating two heuristic metaschemas, Journal of Biomedical Informatics, v.41 n.2, p.293-317, April, 2008

INDEX TERMS

Primary Classification:
G. Mathematics of Computing
G.2 DISCRETE MATHEMATICS

Additional Classification:
F. Theory of Computation
F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
F.2.2 Nonnumerical Algorithms and Problems
Subjects: Computations on discrete structures

General Terms:
Algorithms, Performance, Theory, Verification

Collaborative Colleagues:

Ronald I. Becker: colleagues

Stephen R. Schach: colleagues

Yehoshua Perl: colleagues

Peer to Peer - Readers of this Article have also read:

Constructing reality Proceedings of the 11th annual international conference on Systems documentation
Douglas A. Powell , Norman R. Ball , Mansel W. Griffiths
Data structures for quadtree approximation and compression Communications of the ACM 28, 9
Hanan Samet
A hierarchical single-key-lock access control using the Chinese remainder theorem Proceedings of the 1992 ACM/SIGAPP Symposium on Applied computing
Kim S. Lee , Huizhu Lu , D. D. Fisher
An intelligent component database for behavioral synthesis Proceedings of the 27th ACM/IEEE Design Automation Conference on
Gwo-Dong Chen , Daniel D. Gajski
The GemStone object database management system Communications of the ACM 34, 10
Paul Butterworth , Allen Otis , Jacob Stein

Adobe Acrobat

QuickTime

Windows Media Player

Real Player