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

Persistence, offline algorithms, and space compaction

  • Author(s): Eppstein, David
  • et al.
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
Current View