ACM Portal
  Subscribe (Full Service)    Register (Limited Service, Free)    Login
  Search:   The ACM Digital Library   The Guide
  
ACM Home Page
Please provide us with feedback. Feedback
Worst-case Analysis of Set Union Algorithms
Full text PdfPdf (1.62 MB)
Source Journal of the ACM (JACM) archive
Volume 31 ,  Issue 2  (April 1984) table of contents
Pages: 245 - 281  
Year of Publication: 1984
ISSN:0004-5411
Authors
Robert E. Tarjan  AT&T Bell Laboratories, Murray Hill, New Jersey
Jan van Leeuwen  University of Utrecht, Utrecht, The Netherlands
Publisher
ACM  New York, NY, USA
Bibliometrics
Downloads (6 Weeks): 50,   Downloads (12 Months): 188,   Citation Count: 52
Additional Information:

references   cited by   index terms   review   collaborative colleagues  

Tools and Actions: Request Permissions Request Permissions    Review this Article  
DOI Bookmark: Use this link to bookmark this Article: http://doi.acm.org/10.1145/62.2160
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
ACKERMANN, W. Zum Hilbertschen Aufbau tier reellen Zahlen. Math. Ann. 99 (1928), i |$-!33.
 
2
Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
 
3
BANACHOWSKI, L. A complement to Tarjan's result about the lower bound on the complexity of the set union problem. Inf. Process. Lett. 11 (1980), 59-65.
 
4
DUKSTRA, E.W. A Discipline of Programming. Prentice-Hall, Englewood Cliffs, N.J., 1976.
 
5
FISCHER, M.J.Efficiency of equivalence algorithms. In Complexity of Computer Computations, R. E. Miller and J. W. Thatcher, Eds. Plenum Press, New York, 1972, pp. 153-168.
6
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  [doi>10.1145/800061.808753]
7
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]
 
8
HOPCaOFr, J.E., AND ULLMAN, J.D. Set-merging algorithms. SIAM J. Comlmt. 2 (1973), 294- 303.
 
9
LAO, M.J. A new data structure for the union-find problem. IrOn. Process. Lett. 9 (1979), 39-45.
10
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]
 
11
TAIUAN, R.E.A class of algorithms which require nonlinear time to maintain disjoint seas. J. Comput. Syst. Scl. 18 (1979), 110-127.
12
Robert Endre Tarjan, Applications of Path Compression on Balanced Trees, Journal of the ACM (JACM), v.26 n.4, p.690-715, Oct. 1979  [doi>10.1145/322154.322161]
 
13
VAN LEEUWEN, J., AND VAN DER WEIDE, T.Alternative path compression techniques, Tech. Rcp. RUU-CS-77-3, Rijksuniversiteit Utrecht, Utrecht, The Netherlands, 1977.
 
14
VAN DER WEIDE, T Datastructures: An Axiomatw Approach and the Use of Binomial Trees in Developing and Analyzing Algorithms. Mathematisch Centrum, Amsterdam, 1980.

CITED BY  52
Haim Kaplan , Robert E. Tarjan, Purely functional, real-time deques with catenation, Journal of the ACM (JACM), v.46 n.5, p.577-603, Sept. 1999
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
Wagner Toledo Corrêa , Robert J. Jensen , Craig E. Thayer , Adam Finkelstein, Texture mapping for cel animation, Proceedings of the 25th annual conference on Computer graphics and interactive techniques, p.435-446, July 1998
Haim Kaplan , Nira Shafrir , Robert E. Tarjan, Meldable heaps and boolean union-find, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada
J. A. La Poutré, New techniques for the union-find problem, Proceedings of the first annual ACM-SIAM symposium on Discrete algorithms, p.54-63, January 22-24, 1990, San Francisco, California, United States
Zvi Galil , Giuseppe F. Italiano, Fully dynamic algorithms for edge connectivity problems, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.317-327, May 05-08, 1991, New Orleans, Louisiana, United States
Vugranam C. Sreedhar , Guang R. Gao , Yong-Fong Lee, A new framework for elimination-based data flow analysis using DJ graphs, ACM Transactions on Programming Languages and Systems (TOPLAS), v.20 n.2, p.388-435, March 1998
M. Fredman , M. Saks, The cell probe complexity of dynamic data structures, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.345-354, May 14-17, 1989, Seattle, Washington, United States
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
Richard J. Anderson, Primitives for asynchronous list compression, Proceedings of the fourth annual ACM symposium on Parallel algorithms and architectures, p.199-208, June 29-July 01, 1992, San Diego, California, United States
Adam L. Buchsbaum , Robert E. Tarjan, Confluently persistent deques via data structuaral bootstrapping, Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, p.155-164, January 25-27, 1993, Austin, Texas, United States
Harold N. Gabow , Haim Kaplan , Robert E. Tarjan, Unique maximum matching algorithms, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.70-78, May 01-04, 1999, Atlanta, Georgia, 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
B Bollobás , I Simon, On the expected behavior of disjoint set union algorithms, Proceedings of the seventeenth annual ACM symposium on Theory of computing, p.224-231, May 06-08, 1985, Providence, Rhode Island, United States
Bowen Alpern , Roger Hoover , Barry K. Rosen , Peter F. Sweeney , F. Kenneth Zadeck, Incremental evaluation of computational circuits, Proceedings of the first annual ACM-SIAM symposium on Discrete algorithms, p.32-42, January 22-24, 1990, San Francisco, California, United States
J. A. La Poutré, Lower bounds for the union-find and the split-find problem on pointer machines, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.34-44, May 13-17, 1990, Baltimore, Maryland, United States
Ronald I. Greenberg, Finding connected components on a scan line array processor, Proceedings of the seventh annual ACM symposium on Parallel algorithms and architectures, p.195-202, June 24-26, 1995, Santa Barbara, California, United States
Kai Li , Paul Hudak, Memory coherence in shared virtual memory systems, Proceedings of the fifth annual ACM symposium on Principles of distributed computing, p.229-239, August 11-13, 1986, Calgary, Alberta, Canada
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
Giuseppe Amato , Giuseppe Cattaneo , Giuseppe F. Italiano, Experimental analysis of dynamic minimum spanning tree algorithms, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.314-323, January 05-07, 1997, New Orleans, Louisiana, United States
Lenwood S. Heath , Arnold L. Rosenberg , Bruce T. Smith, The physical mapping problem for parallel architectures, Journal of the ACM (JACM), v.35 n.3, p.603-634, July 1988
Marc J. van Kreveld , Mark H. Overmars, Union-copy structures and dynamic segment trees, Journal of the ACM (JACM), v.40 n.3, p.635-652, July 1993
Stephen Alstrup , Amir M. Ben-Amram , Theis Rauhe, Worst-case and amortised optimality in union-find (extended abstract), Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.499-506, May 01-04, 1999, Atlanta, Georgia, United States
Kai Li , Paul Hudak, Memory coherence in shared virtual memory systems, ACM Transactions on Computer Systems (TOCS), v.7 n.4, p.321-359, Nov. 1989
Robert Joseph Fowler, The complexity of using forwarding addresses for decentralized object finding, Proceedings of the fifth annual ACM symposium on Principles of distributed computing, p.108-120, August 11-13, 1986, Calgary, Alberta, Canada
Wei Yi Liu , Ning Song, Fuzzy functional dependencies and Bayesian networks, Journal of Computer Science and Technology, v.18 n.1, p.56-66, January 2003
Alain Giorgetti, An asymptotic study for path reversal, Theoretical Computer Science, v.299 n.1-3, p.585-602, 18 April 2003
Kenji Suzuki , Isao Horiba , Noboru Sugie, Linear-time connected-component labeling based on sequential local operations, Computer Vision and Image Understanding, v.89 n.1, p.1-23, January 2003
Henning Fernau, Identification of function distinguishable languages, Theoretical Computer Science, v.290 n.3, p.1679-1711, 3 January 2003
Ittai Abraham , Danny Dolev, Asynchronous resource discovery, Proceedings of the twenty-second annual symposium on Principles of distributed computing, p.143-150, July 13-16, 2003, Boston, Massachusetts
Vladimir Kovalevsky, Multidimensional cell lists for investigating 3-manifolds, Discrete Applied Mathematics, v.125 n.1, p.25-43, 15 January 2003
Wei Yi Liu , Ning Song, A fuzzy approach to classification of text documents, Journal of Computer Science and Technology, v.18 n.5, p.640-647, September 2003
Michael B. Dillencourt , Hannan Samet , Markku Tamminen, A general approach to connected-component labeling for arbitrary image representations, Journal of the ACM (JACM), v.39 n.2, p.253-280, April 1992
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
Daniel Dominic Sleator , Robert Endre Tarjan, Self-adjusting binary search trees, Journal of the ACM (JACM), v.32 n.3, p.652-686, July 1985
Hanan Samet , Markku Tamminen, Efficient Component Labeling of Images of Arbitrary Dimension Represented by Linear Bintrees, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.10 n.4, p.579-586, July 1988
Camil Demetrescu , Irene Finocchi , Giuseppe F. Italiano , Stefan Näher, Visualization in algorithm engineering: tools and techniques, Experimental algorithmics: from algorithm design to robust and efficient software, Springer-Verlag New York, Inc., New York, NY, 2002
Ittai Abraham , Danny Dolev, Asynchronous resource discovery, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.50 n.10, p.1616-1629, 14 July 2006
Daniel Dominic Sleator , Robert Endre Tarjan, Self-adjusting binary trees, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.235-245, December 1983
Haim Kaplan , Nira Shafrir , Robert E. Tarjan, Union-find with deletions, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.19-28, January 06-08, 2002, San Francisco, California
Guojing Cong , David A. Bader, Designing irregular parallel algorithms with mutual exclusion and lock-free protocols, Journal of Parallel and Distributed Computing, v.66 n.6, p.854-866, June 2006
Pankaj K. Agarwal , Lars Arge , Ke Yi, I/O-efficient batched union-find and its applications to terrain analysis, Proceedings of the twenty-second annual symposium on Computational geometry, June 05-07, 2006, Sedona, Arizona, USA
Ran Mendelson , Robert E. Tarjan , Mikkel Thorup , Uri Zwick, Melding priority queues, ACM Transactions on Algorithms (TALG), v.2 n.4, p.535-556, October 2006
Tom Schrijvers , Thom Frühwirth, Optimal union-find in Constraint Handling Rules, Theory and Practice of Logic Programming, v.6 n.1-2, p.213-224, January 2006
Michael D. Adams , R. Kent Dybvig, Efficient nondestructive equality checking for trees and graphs, ACM SIGPLAN Notices, v.43 n.9, September 2008
Lifeng He , Yuyan Chao , Kenji Suzuki , Kesheng Wu, Fast connected-component labeling, Pattern Recognition, v.42 n.9, p.1977-1987, September, 2009
S. Biasotti , D. Giorgi , M. Spagnuolo , B. Falcidieno, Size functions for comparing 3D models, Pattern Recognition, v.41 n.9, p.2855-2873, September, 2008
S. Biasotti , L. De Floriani , B. Falcidieno , P. Frosini , D. Giorgi , C. Landi , L. Papaleo , M. Spagnuolo, Describing shapes by geometrical-topological properties of real functions, ACM Computing Surveys (CSUR), v.40 n.4, p.1-87, October 2008
Jon Sneyers , Tom Schrijvers , Bart Demoen, The computational power and complexity of constraint handling rules, ACM Transactions on Programming Languages and Systems (TOPLAS), v.31 n.2, p.1-42, February 2009
Khalil Djelloul, From exponential to almost linear decomposability of finite or infinite trees, Proceedings of the 2009 ACM symposium on Applied Computing, March 08-12, 2009, Honolulu, Hawaii
Alan M. Frisch, Using model theory to specify AI programs, Proceedings of the 9th international joint conference on Artificial intelligence, p.148-154, August 18-23, 1985, Los Angeles, California

INDEX TERMS

Classification:
  E. Data
  E.1 DATA STRUCTURES
      Subjects: Trees

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

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Combinatorial algorithms
      G.2.2 Graph Theory
          Subjects: Graph algorithms


General Terms:
Algorithms, Performance, Theory, Verification


REVIEW

"William Fennell Smyth : Reviewer"

A typical set union problem is to determine a minimum-cost spanning tree (for example, spanning the nodes of a communications network). A Set Union Algorithm (SUA) consists of some sequence of the following fundamental operations: more...

Collaborative Colleagues:
Robert E. Tarjan: colleagues
Jan van Leeuwen: colleagues

The ACM Portal is published by the Association for Computing Machinery. Copyright © 2009 ACM, Inc.
Terms of Usage   Privacy Policy   Code of Ethics   Contact Us

Useful downloads: Adobe Acrobat    QuickTime    Windows Media Player    Real Player