Disjoint-set data structure: Difference between revisions

Revision as of 04:31, 24 December 2005

Revision as of 04:34, 24 December 2005

Line 99:

== History ==

While the ideas used in disjoint-set forests have long been familiar, [[Robert Tarjan]] was the first to prove the upper bound (and a restricted version of the lower bound) in terms of the inverse Ackermann function. Until this time the best bound on the time per operation, proven by Hopcroft and Ullman, was O(log^* n), the [[iterated logarithm]] of n, another slowly-growing function (but not quite as slow as the inverse Ackermann function). Tarjan and van Leeuwen also developed one-pass '''Find''' algorithms that are more efficient in practice. The algorithm was made well-known by the popular textbook ''Introduction to Algorithms'', listed in the references.{{ref|IntroductionToAlgorithms}}

== External links ==

Line 121:

* {{note|GallerFisher}}Bernard A. Galler and Michael J. Fisher. An improved equivalence algorithm. Communications of the ACM, Volume 7, Issue 5 (May 1964), pages 301-303. The paper originating disjoint-set forests. [http://portal.acm.org/citation.cfm?doid=364099.364331 ACM Digital Library]

* {{note|IntroductionToAlgorithms}} [[Thomas H. Cormen]], [[Charles E. Leiserson]], [[Ronald L. Rivest]], and [[Clifford Stein]]. ''[[Introduction to Algorithms]]'', Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0262032937. Chapter 21: Data structures for Disjoint Sets, pp.498–524.

* Zvi Galil and Giuseppe F. Italiano. Data structures and algorithms for disjoint set union problems", ACM Computing Surveys, Volume 23, Issue 3 (September 1991), pages 319-344. [http://portal.acm.org/citation.cfm?id=116878 ACM Digital Library]