Donald Bren School of Information and Computer Sciences

We consider dynamic data structures in which updates rebuild a static solution. Space bounds for persistent versions of these structures can often be reduced by using an offiine persistent data structure in place of the static solution. We apply this technique to decomposable search problems, to dynamic linear programming, and to maintaining the minimum spanning tree in a dynarnic graph. Our algorithms admit trade-offs of update time vs. query time, and of time vs. space.