The recognition of union trees

DOI10.1016/0020-0190(93)90037-AMaRDI QIDQ2365813zbMATH OpenOpenAlexFDO

Authors Leizhen Cai

Publication date 29 June 1993

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0020-0190(93)90037-a

zbMATH Keywords

design of algorithmsdisjoint-set unionpolynomial-time algorithmrooted treesunion tree-recognition

Mathematics Subject Classification ID

Trees (05C05) Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Recognizing union-find trees is NP-complete, even without rank info
• Recognizing union-find trees built up using union-by-rank strategy is NP-complete
• Recognizing union-find trees is NP-complete
• A linear-time algorithm for a special case of disjoint set union
• Complexity of algorithm and operations on trees

Cites work

• An improved equivalence algorithm
• scientific article; zbMATH DE number 3936534 (Why is no real title available?)
• scientific article; zbMATH DE number 3449757 (Why is no real title available?)
• Worst-case Analysis of Set Union Algorithms

Cited in

(6)

• Efficient Union-Find for planar graphs and other sparse graph classes
• Recognizing union-find trees is NP-complete
• Recognizing union-find trees built up using union-by-rank strategy is NP-complete
• Postorder Disjoint Set Union is Linear
• Recognizing union-find trees is NP-complete, even without rank info
• A reciprocal confluence tree unit and its applications

This page was built for publication: The recognition of union trees

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