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, in 1975. 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 while retaining the same worst-case complexity.
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.
Read more about this topic: Disjoint-set Data Structure
Famous quotes containing the word history:
“America is the only nation in history which miraculously has gone directly from barbarism to degeneration without the usual interval of civilization.”
—Georges Clemenceau (1841–1929)
“The history of any nation follows an undulatory course. In the trough of the wave we find more or less complete anarchy; but the crest is not more or less complete Utopia, but only, at best, a tolerably humane, partially free and fairly just society that invariably carries within itself the seeds of its own decadence.”
—Aldous Huxley (1894–1963)
“Indeed, the Englishman’s history of New England commences only when it ceases to be New France.”
—Henry David Thoreau (1817–1862)