scientific article; zbMATH DE number 3907792

From MaRDI portal
Publication:3685219





[For the entire collection see Zbl 0561.00020.] We give an algorithm for the disjoint set union problem, within the class of algorithms defined by Tarjan, which has O(log n/log log n) single- operation time complexity in the worst-case. Also we define a class of algorithms for the disjoint set union problem, which includes the class of algorithms defined by Tarjan. We prove that any algorithm from this class has at least \(\Omega\) (log n/log log n) single-operation time complexity in the worst-case.











This page was built for publication:

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