Fast decremental tree sums in forests

Benjamin Aram Berendsohn, Marek Sokołowski · 2026

Read Fast decremental tree sums in forests by Benjamin Aram Berendsohn, Marek Sokołowski (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-2605-06555.txt.

Description

Benjamin Aram Berendsohn and Marek Sokołowski study dynamic forests where edges only get deleted. The task is maintaining sums of vertex weights, either over a whole tree component or over a rooted subtree, while weights also update. Standard structures answer in logarithmic time and even allow insertions, so the question is whether deletion-only work can go faster.

For tree sums they give a structure with near-constant time per operation, constant time for unweighted forests, and an asymptotically optimal algorithm in a group model. For subtree sums they prove tight bounds across several variants. The results sharpen what decremental data structures can achieve.

Catalog record

CREATORBenjamin Aram Berendsohn, Marek Sokołowski
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE120 KB
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.06555

Browse the full library · About the Tower of Babel