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
| CREATOR | Benjamin Aram Berendsohn |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 146 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2602-15977