Sum-of-Local-Effects Data Structures for Separable Graphs

It is not difficult to think of applications that can be modelled as graph problems in which placing some facility or commodity at a vertex has some positive or negative effect on the values of all the vertices out to some distance, and we want to be able to calculate quickly the cumulative effect on any vertex’s value at any time or the list of the most beneficial or most detrimential effects on a vertex. In this paper we show how, given an edge-weighted graph with constant-size separators, we can support the following operations in time polylogarithmic in the number of vertices and the number of facilities placed on the vertices, where distances between vertices are measured with respect to edge weights: The weights of the facilities and the operation that \(\textsc {Sum}\) uses to “sum” them must form a semigroup. For \(\textsc {Top}\) queries, the weights must be drawn from a total order.