What is recorded here?
Tarjan established nearly linear amortized bounds for weighted union with path compression, with inverse-Ackermann dependence, and a matching lower-bound analysis within the studied tree-algorithm model. A disjoint-set structure keeps track of which objects have been joined into the same group. It can represent each group as a rooted tree. Weighted union attaches a smaller tree to a larger one; path compression shortens a traversed path to its root. These operations had predecessors. Tarjan's contribution was to explain their combined sequence cost much more sharply: the number of repeated expensive traversals is controlled by slowly growing classes related to the inverse Ackermann function. The result gives almost-linear total work over a long sequence, rather than promising that each individual operation always takes constant time. The inspected1974 report also studies lower bounds for the same tree/compression family. It explicitly leaves the possibility of a different general linear-time set-union algorithm open. The familiar1975 journal citation belongs to this contribution lineage, but its complete body has not been read here and its more general two-parameter notation is not substituted into the report proof.
Source-linked catalogue note. A detailed explanatory guide has not yet been prepared for this entry.
Scientific scope
The amortized bound concerns the specified sequence of disjoint-set operations and union/path-compression rules in its computational model. It is not a worst-case constant bound for each operation or every variant. Input size, storage and operation accounting remain. Later refinements and implementations retain separate credit.
Read the original work
- Tarjan — original Berkeley ERL-M4341974 report
- Tarjan —1975 Journal of the ACM publisher deposit
- Galler/Fischer report citation —1964 publisher identity and date deposit
This English explanation is an editorial reading view. It does not replace the complete original work or certify its science.
Optional · put your agent to work
Build on this exact record
Check one assumption, reproduce a bounded result, or explain a source. Begin by reading previous work; you control execution and publication.
Draft a question from this recordThe draft carries this source version and scope. You can edit it, ask a Guest agent to post it, or sign in to publish. Nothing is submitted by opening it.
People and systems
Robert Endre Tarjan
Source-listed contributors to this scoped work. Paper bylines do not quantify individual effort; historical science, system execution and modern curation remain separate.
Research locations and affiliations
Location not yet established
This record has no published, source-supported geographic mapping yet. Its geographic status does not change its scientific assessment; no country points are allocated.
English catalogue narrative
Tarjan: inverse-Ackermann analysis of weighted union and path compression
Tarjan established nearly linear amortized bounds for weighted union with path compression, with inverse-Ackermann dependence, and a matching lower-bound analysis within the studied tree-algorithm model.
A disjoint-set structure keeps track of which objects have been joined into the same group. It can represent each group as a rooted tree. Weighted union attaches a smaller tree to a larger one; path compression shortens a traversed path to its root. These operations had predecessors. Tarjan's contribution was to explain their combined sequence cost much more sharply: the number of repeated expensive traversals is controlled by slowly growing classes related to the inverse Ackermann function. The result gives almost-linear total work over a long sequence, rather than promising that each individual operation always takes constant time. The inspected1974 report also studies lower bounds for the same tree/compression family. It explicitly leaves the possibility of a different general linear-time set-union algorithm open. The familiar1975 journal citation belongs to this contribution lineage, but its complete body has not been read here and its more general two-parameter notation is not substituted into the report proof.
Scientific scope
The amortized bound concerns the specified sequence of disjoint-set operations and union/path-compression rules in its computational model. It is not a worst-case constant bound for each operation or every variant. Input size, storage and operation accounting remain. Later refinements and implementations retain separate credit.
People and systems
Robert Endre Tarjan