A complement to Tarjan's result about the lower bound on the complexity of the set union problem

DOI10.1016/0020-0190(80)90001-0zbMath0453.68039OpenAlexW2003824261MaRDI QIDQ1149259

Lech Banachowski

Publication date: 1980

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

Full work available at URL: https://doi.org/10.1016/0020-0190(80)90001-0

zbMATH Keywords

set union problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Discrete mathematics in relation to computer science (68R99)

Related Items (5)

A lower bound on the single-operation worst-case time complexity of the union-find problem on intervals ⋮ Memory management for Union-Find algorithms ⋮ Two linear time Union--Find strategies for image processing ⋮ Efficient Union-Find for planar graphs and other sparse graph classes ⋮ ALGORITHMS FOR K-DISJOINT MAXIMUM SUBARRAYS

Cites Work

• Unnamed Item
• A class of algorithms which require nonlinear time to maintain disjoint sets
• Efficiency of a Good But Not Linear Set Union Algorithm

This page was built for publication: A complement to Tarjan's result about the lower bound on the complexity of the set union problem