Postorder Disjoint Set Union is Linear

DOI10.1137/0219060MaRDI QIDQ3495655zbMATH OpenOpenAlexFDO

Authors Joan M. Lucas

Publication date 1990

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/0219060

zbMATH Keywords

data structuresdisjoint set union problempairing heapsplay treeunion-find

Mathematics Subject Classification ID

Data structures (68P05) Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05)

Recommendations

• A linear-time algorithm for a special case of disjoint set union
• On the Single-Operation Worst-Case Time Complexity of the Disjoint Set Union Problem
• scientific article; zbMATH DE number 3907792
• The recognition of union trees
• The Set Union Problem with Unlimited Backtracking

Cited in

(2)

• Recognizing union-find trees built up using union-by-rank strategy is NP-complete
• The longest common substring problem

This page was built for publication: Postorder Disjoint Set Union is Linear

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3495655)