Universally Optimal Decremental Tree Minima

Benjamin Aram Berendsohn · 2026

Read Universally Optimal Decremental Tree Minima by Benjamin Aram Berendsohn (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2602-15977.txt.

Description

Berendsohn extends universal optimality from algorithms to data structures. An algorithm earns the label when it is optimal for every input graph under the worst weights, beating even methods tuned to a single graph. The paper asks whether a data structure can meet the same bar, and answers with a dynamic forest problem.

The task is to track the lightest vertex of every tree while edges are deleted. In general this needs logarithmic time per step, yet on a path it takes constant time. Berendsohn decomposes any forest into paths and pairs that trick with splay trees to handle a sorting subproblem, achieving optimal total time for every fixed forest and operation count. The same design adapts to Cartesian trees, path minima, bottleneck queries, edge weights, and semigroup sums.

Catalog record

CREATORBenjamin Aram Berendsohn
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE146 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2602-15977

Browse the full library · About the Tower of Babel