Decremental tree sums.

Abstract: 

In this talk, I will discuss the following semi-dynamic graph problem: Maintain a vertex-weighted forest under the following operations: Delete an edge; change the weight of a vertex; and, given a vertex v, return the total weight of all vertices in the same tree as v.

I’ll present the following results from joint work with Marek

Sokołowski.

* A data structure with O(m + n log* n) time for m operations;

* a linear-time data structure for *unweighted* forests;

* and a data structure with (conditionally) optimal, but unknown running time.

At the end, I will briefly speculate on the actual complexity of the problem, and propose some ideas on how to determine it.