Applications of Path Compression on Balanced Trees

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Applications of Path Compression on Balanced Trees

Full text

Pdf (1.48 MB)

Source

Journal of the ACM (JACM) archive
Volume 26 , Issue 4 (October 1979) table of contents

Pages: 690 - 715

Year of Publication: 1979

ISSN:0004-5411

Author

Robert Endre Tarjan

Department of Computer Science, Stanford University, Stanford, CA

Publisher

ACM New York, NY, USA

Bibliometrics

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

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/322154.322161 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	ACKERMANNN, W Zum Hdbershen Aufbau der reellen Zahlen. Math. Ann 99 (1928), 118-133
	2	Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
	3	AHO, A.V, HOPCROFT, J.E, AND ULLMAN, J.D On computing least common ancestors in trees SIAM J. Comptng. 5 (1976), 115-132.
	4	Auo, A V., AtqD UtJ~tAN, J D. Node listings for reducible flow graphs. J Comptr Syst Sci. 13 (1976), 286- 299
	5	Bruce W. Arden , Bernard A. Galler , Robert M. Graham, An algorithm for equivalence declarations, Communications of the ACM, v.4 n.7, p.310-314, July 1961 [doi>10.1145/366622.366626]
	6	CHERITON, D, AND TARJAN, R E Fmdmg minimum spannmg trees SIAM J Comptng. 5 (1976), 724-742
	7	CmN, FY, AND HOUCK, D J Algorithms for updating minimal spanning trees. J. Comptr Syst Sci 16 (1978), 333-344
	8	CHV.~TAL, V., KLARNER, D.A., AND KNUTH, D E Selected combinatorial research problems STAN-CS-72-
	9	FARROW, R Efficlent on-line evaluation of funcUons defined on paths m trees. Tech. Re~. 476-093-17, Dept 292, Comptr Sc~ Dept, Stanford U, Stanford, Cahf, 1972 Math Sc~, R~ce U, Houston, Tex, 1977
	10	FISCHER, M J. Efficiency of eqmvalence algorithms. In Complexity of Computauons, R E Miller and J W Thatcher, Eds, Plenum Press, New York, 1972, pp 153-168
	11	Amelia Fong , John Kam , Jeffrey Ullman, Application of lattice algebra to loop optimization, Proceedings of the 2nd ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.1-9, January 20-22, 1975, Palo Alto, California [doi>10.1145/512976.512977]
	12	Benrard A. Galler , Michael J. Fisher, An improved equivalence algorithm, Communications of the ACM, v.7 n.5, p.301-303, May 1964 [doi>10.1145/364099.364331]
	13	Susan L. Graham , Mark Wegman, A Fast and Usually Linear Algorithm for Global Flow Analysis, Journal of the ACM (JACM), v.23 n.1, p.172-202, Jan. 1976 [doi>10.1145/321921.321939]
	14	HOPCROFT, J E Private commumcatlon.
	15	HOPCROFT, J E., AND ULLMAN, J D Set-merging algonthms. SIAM J Comptng 2 (1973), 294-303
	16	Hu,T C Integer Programming and Network Flows. Addison-Wesley, Reading, Mass., 1969, pp 129-150.
	17	K. W. Kennedy, Node listings applied to data flow analysis, Proceedings of the 2nd ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.10-21, January 20-22, 1975, Palo Alto, California [doi>10.1145/512976.512978]
	18	Donald E. Knuth, The art of computer programming, volume 1 (3rd ed.): fundamental algorithms, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1997
	19	Thomas Lengauer , Robert Endre Tarjan, A fast algorithm for finding dominators in a flowgraph, ACM Transactions on Programming Languages and Systems (TOPLAS), v.1 n.1, p.121-141, July 1979 [doi>10.1145/357062.357071]
	20	PATERSON, M Unpubhshed report, U. of Warwick, Conventry, England, 1972.
	21	TARJAN, R.E Depth-first search and hnear graph algorithms SlAM Z Comptng. 1 (1972), 146-160.
	22	TAR/AN, R.E Finding dominators m directed~raphs. SlAM J. Comptng 5 (1974), 62-89.
	23	TARJAN, R.E. Testing flow graph reduclbdlty J Comptr and Syst. Scz 9 (1974), 355-365
	24	Robert Endre Tarjan, Efficiency of a Good But Not Linear Set Union Algorithm, Journal of the ACM (JACM), v.22 n.2, p.215-225, April 1975 [doi>10.1145/321879.321884]
	25	Robert E Tarjan, Applications of path compression on balanced trees., Stanford University, Stanford, CA, 1975
	26	Robert E Tarjan, Solving path problems on directed graphs., Stanford University, Stanford, CA, 1975
	27	TAt~Ar~, R.E. Graph theory and Gaussmn elLmmaUon In Sparse Matrix Computatwns, J R. Bunch and D.J. Rose, Eds., Academic Press, New York, 1976, pp. 3-22
	28	TAR/AN, R E A class of algorithms which reqmre non-hnear tune to maintain disjoint sets TO appear in J. Comptr and Syst. Scl
	29	TAR/AN, R.E ComplexRy of monotone networks for computing conjunctions Annals Discrete Math. 2 (1978), 121-133
	30	ULLMAN, J.D. A fast algonthm for the ehmmation of common subexpresstons. Aeta Informatwa 2 (1973), 191-213.
	31	YAO, A.C. An O({EI log log I VI) algonthm for finding minimum spanning trees. Inform. Processing Letters 4 (1975), 21-23

CITED BY 54

	Jens Knoop , Oliver Rüthing , Bernhard Steffen, Lazy code motion, ACM SIGPLAN Notices, v.27 n.7, p.224-234, July 1992
	David Eppstein , S. Muthukrishnan, Internet packet filter management and rectangle geometry, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.827-835, January 07-09, 2001, Washington, D.C., United States
	Adam L. Buchsbaum , Haim Kaplan , Anne Rogers , Jeffery R. Westbrook, Linear-time pointer-machine algorithms for least common ancestors, MST verification, and dominators, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.279-288, May 24-26, 1998, Dallas, Texas, United States
	Harold N. Gabow , Robert Endre Tarjan, A linear-time algorithm for a special case of disjoint set union, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.246-251, December 1983
	Dan Gusfield , Dalit Naor, Efficient algorithms for generalized cut trees, Proceedings of the first annual ACM-SIAM symposium on Discrete algorithms, p.422-433, January 22-24, 1990, San Francisco, California, United States
	Harold N. Gabow, Data structures for weighted matching and nearest common ancestors with linking, Proceedings of the first annual ACM-SIAM symposium on Discrete algorithms, p.434-443, January 22-24, 1990, San Francisco, California, United States
	Ali A. Kooshesh , Robert R. Crawford, Yet another efficient algorithm for replacing the edges of a minimum spanning tree, Proceedings of the 1996 ACM 24th annual conference on Computer science, p.76-78, February 15-18, 1996, Philadelphia, Pennsylvania, United States
	Mark Wegman, Summarizing graphs by regular expressions, Proceedings of the 10th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.203-216, January 24-26, 1983, Austin, Texas
	Adam L. Buchsbaum , Haim Kaplan , Anne Rogers , Jeffery R. Westbrook, A new, simpler linear-time dominators algorithm, ACM Transactions on Programming Languages and Systems (TOPLAS), v.20 n.6, p.1265-1296, Nov. 1998
	Jens Knoop , Oliver Rüthing , Bernhard Steffen, The power of assignment motion, ACM SIGPLAN Notices, v.30 n.6, p.233-245, June 1995
	Daniel D. Sleator , Robert Endre Tarjan, A data structure for dynamic trees, Proceedings of the thirteenth annual ACM symposium on Theory of computing, p.114-122, May 11-13, 1981, Milwaukee, Wisconsin, United States
	Martin Loebl , Jaroslav Nešetřil, Linearity and unprovability of set union problem, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.360-366, May 02-04, 1988, Chicago, Illinois, United States
	Thomas Lengauer , Robert Endre Tarjan, A fast algorithm for finding dominators in a flowgraph, ACM Transactions on Programming Languages and Systems (TOPLAS), v.1 n.1, p.121-141, July 1979
	Mingdong Feng , Charles E. Leiserson, Efficient detection of determinacy races in Cilk programs, Proceedings of the ninth annual ACM symposium on Parallel algorithms and architectures, p.1-11, June 23-25, 1997, Newport, Rhode Island, United States
	Jens Knoop , Oliver Rüthing , Bernhard Steffen, Optimal code motion: theory and practice, ACM Transactions on Programming Languages and Systems (TOPLAS), v.16 n.4, p.1117-1155, July 1994
	David R. Karger , Philip N. Klein , Robert E. Tarjan, A randomized linear-time algorithm to find minimum spanning trees, Journal of the ACM (JACM), v.42 n.2, p.321-328, March 1995
	Robert Endre Tarjan, Fast Algorithms for Solving Path Problems, Journal of the ACM (JACM), v.28 n.3, p.594-614, July 1981
	Guang-Ien Cheng , Mingdong Feng , Charles E. Leiserson , Keith H. Randall , Andrew F. Stark, Detecting data races in Cilk programs that use locks, Proceedings of the tenth annual ACM symposium on Parallel algorithms and architectures, p.298-309, June 28-July 02, 1998, Puerto Vallarta, Mexico
	Keith D. Cooper , Ken Kennedy, Efficient computation of flow insensitive interprocedural summary information, ACM SIGPLAN Notices, v.19 n.6, p.247-258, June 1984
	Peng Tu , David Padua, Efficient building and placing of gating functions, ACM SIGPLAN Notices, v.30 n.6, p.47-55, June 1995
	Adam L. Buchsbaum , Jefferey R. Westbrook, Maintaining hierarchical graph views, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.566-575, January 09-11, 2000, San Francisco, California, United States
	Vincenzo Liberatore, Matroid decomposition methods for the set maxima problem, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.400-409, January 25-27, 1998, San Francisco, California, United States
	Bruno Blanchet, Escape analysis: correctness proof, implementation and experimental results, Proceedings of the 25th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.25-37, January 19-21, 1998, San Diego, California, United States
	Seth Pettie , Vijaya Ramachandran, An optimal minimum spanning tree algorithm, Journal of the ACM (JACM), v.49 n.1, p.16-34, January 2002
	Michael A. Bender , Giridhar Pemmasani , Steven Skiena , Pavel Sumazin, Finding least common ancestors in directed acyclic graphs, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.845-854, January 07-09, 2001, Washington, D.C., United States
	D Harel, A linear algorithm for finding dominators in flow graphs and related problems, Proceedings of the seventeenth annual ACM symposium on Theory of computing, p.185-194, May 06-08, 1985, Providence, Rhode Island, United States
	Robert E. Tarjan , Jan van Leeuwen, Worst-case Analysis of Set Union Algorithms, Journal of the ACM (JACM), v.31 n.2, p.245-281, April 1984
	Harold N. Gablow , Robert E. Tarjan, Faster scaling algorithms for general graph matching problems, Journal of the ACM (JACM), v.38 n.4, p.815-853, Oct. 1991
	Philip N. Klein , Robert E. Tarjan, A randomized linear-time algorithm for finding minimum spanning trees, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.9-15, May 23-25, 1994, Montreal, Quebec, Canada
	Alain Deutsch, On the complexity of escape analysis, Proceedings of the 24th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.358-371, January 15-17, 1997, Paris, France
	Michael L. Fredman , Robert Endre Tarjan, Fibonacci heaps and their uses in improved network optimization algorithms, Journal of the ACM (JACM), v.34 n.3, p.596-615, July 1987
	Hans L. Bodlaender , Gerard Tel , Nicola Santoro, Trade-offs in non-reversing diameter, Nordic Journal of Computing, v.1 n.1, p.111-134, Spring 1994
	G. Ramalingam, Identifying loops in almost linear time, ACM Transactions on Programming Languages and Systems (TOPLAS), v.21 n.2, p.175-188, March 1999
	Harold N. Gabow, Better performance bounds for finding the smallest k-edge connected spanning subgraph of a multigraph, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
	Adam L. Buchsbaum , Haim Kaplan , Anne Rogers , Jeffery R. Westbrook, Corrigendum: a new, simpler linear-time dominators algorithm, ACM Transactions on Programming Languages and Systems (TOPLAS), v.27 n.3, p.383-387, May 2005
	Juha Kärkkäinen , Gonzalo Navarro , Esko Ukkonen, Approximate string matching on Ziv-Lempel compressed text, Journal of Discrete Algorithms, v.1 n.3-4, p.313-338, June 2003
	Loukas Georgiadis , Robert E. Tarjan, Finding dominators revisited: extended abstract, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
	Zvi Galil , Giuseppe F. Italiano, Data structures and algorithms for disjoint set union problems, ACM Computing Surveys (CSUR), v.23 n.3, p.319-344, Sept. 1991
	Michael A. Bender , Martín Farach-Colton , Giridhar Pemmasani , Steven Skiena , Pavel Sumazin, Lowest common ancestors in trees and directed acyclic graphs, Journal of Algorithms, v.57 n.2, p.75-94, November 2005
	Jens Knoop , Oliver Rüthing , Bernhard Steffen, Partial dead code elimination, ACM SIGPLAN Notices, v.29 n.6, p.147-158, June 1994
	Ron K. Cytron , Jeanne Ferrante, Efficiently computing Φ-nodes on-the-fly, ACM Transactions on Programming Languages and Systems (TOPLAS), v.17 n.3, p.487-506, May 1995
	Chen-Hsing Peng , Biing-Feng Wang , Jia-Shung Wang, Recognizing Unordered Depth-First Search Trees of an Undirected Graph in Parallel, IEEE Transactions on Parallel and Distributed Systems, v.11 n.6, p.559-570, June 2000
	Jens Knoop , Oliver Rüthing , Bernhard Steffen, Lazy code motion, ACM SIGPLAN Notices, v.39 n.4, April 2004
	Dwight S. Wilson , Gregory F. Sullivan , Gerald M. Masson, Certification of Computational Results, IEEE Transactions on Computers, v.44 n.7, p.833-847, July 1995
	On loops, dominators, and dominance frontiers, ACM Transactions on Programming Languages and Systems (TOPLAS), v.24 n.5, p.455-490, September 2002
	Greg N. Frederickson, Data structures for on-line updating of minimum spanning trees, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.252-257, December 1983
	Loukas Georgiadis , Robert E. Tarjan, Dominator tree verification and vertex-disjoint paths, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
	Michael A. Bender , Jeremy T. Fineman , Seth Gilbert , Charles E. Leiserson, On-the-fly maintenance of series-parallel relationships in fork-join multithreaded programs, Proceedings of the sixteenth annual ACM symposium on Parallelism in algorithms and architectures, June 27-30, 2004, Barcelona, Spain
	Guido Proietti , Peter Widmayer, A truthful mechanism for the non-utilitarian minimum radius spanning tree problem, Proceedings of the seventeenth annual ACM symposium on Parallelism in algorithms and architectures, July 18-20, 2005, Las Vegas, Nevada, USA
	Amos Korman , Shay Kutten, Distributed verification of minimum spanning trees, Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing, July 23-26, 2006, Denver, Colorado, USA
	Barbara G. Ryder , Marvin C. Paull, Elimination algorithms for data flow analysis, ACM Computing Surveys (CSUR), v.18 n.3, p.277-316, Sept. 1986
	Artur Czumaj , Mirosaw Kowaluk , Andrzej Lingas, Faster algorithms for finding lowest common ancestors in directed acyclic graphs, Theoretical Computer Science, v.380 n.1-2, p.37-46, June, 2007
	P. Flocchini , L. Pagli , G. Prencipe , N. Santoro , P. Widmayer, Computing all the best swap edges distributively, Journal of Parallel and Distributed Computing, v.68 n.7, p.976-983, July, 2008
	Adam L. Buchsbaum , Emden R. Gansner , Cecilia M. Procopiuc , Suresh Venkatasubramanian, Rectangular layouts and contact graphs, ACM Transactions on Algorithms (TALG), v.4 n.1, p.1-28, March 2008