Skip to main content
eScholarship
Open Access Publications from the University of California

Persistence, offline algorithms, and space compaction

Abstract

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.

Main Content
For improved accessibility of PDF content, download the file to your device.
Current View