steak-union - Tumblr blog

[steak-union]

Galil and Italiano

Disjoint-set forests were first described by Bernard A. Galler and Michael J. Fischer in 1964.[2] In 1973, their time complexity was bounded to {\displaystyle O(\log ^{*}(n))}, the iterated logarithm of {\displaystyle n}, by Hopcroft and Ullman.[3] (A proof is available here.) In 1975, Robert Tarjanwas the first to prove the {\displaystyle O(\alpha (n))} (inverse Ackermann function) upper bound on the algorithm's time complexity,[4] and, in 1979, showed that this was the lower bound for a restricted case.[5] In 1989, Fredman and Saks showed that {\displaystyle \Omega (\alpha (n))} (amortized) words must be accessed by any disjoint-set data structure per operation,[6], thereby proving the optimality of the data structure.

In 1991, Galil and Italiano published a survey of data structures for disjoint-sets.[7]

In 1994, Richard J. Anderson and Heather Woll described a parallelized version of Union–Find that never needs to block.[8]

In 2007, Sylvain Conchon and Jean-Christophe Filliâtre developed a persistent version of the disjoint-set forest data structure, allowing previous versions of the structure to be efficiently retained, and formalized its correctness using the proof assistant Coq.[9]However, the implementation is only asymptotic if used ephemerally or if the same version of the structure is repeatedly used with limited backtracking.