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

Efficient optimal pagination of scrolls

  • Author(s): Larmore, L. L.
  • Hirschberg, D. S.
  • et al.

Diehr and Faaland developed an algorithm that finds the minimum sum of key length pagination of a scroll of n items, and which uses O(n lg n) time and O(n) space, solving a problem posed by McCreight. An improved algorithm is given which uses O(n) time and O(n) space.

Main Content
Current View