Paper by Erik D. Demaine

Erik D. Demaine, John Iacono, and Stefan Langerman, “Worst-Case Optimal Tree Layout in External Memory”, Algorithmica, volume 72, number 2, 2015, pages 369–378.

Consider laying out a fixed-topology tree of N nodes into external memory with block size B so as to minimize the worst-case number of block memory transfers required to traverse a path from the root to a node of depth D. We prove that the optimal number of memory transfers is
Θ ({ D / lg (1+B)    when D = O(lg N) ) .
lg N / lg (1 + (B lg N) / D) when D = Ω(lg N) and D = O(B lg N)
D / B when D = Ω(B lg N)

This paper is also available as arXiv:cs.DS/0410048 of the Computing Research Repository (CoRR).

This paper is also available from SpringerLink.

The paper is 10 pages.

The paper is available in PostScript (440k), gzipped PostScript (223k), and PDF (229k).
See information on file formats.
[Google Scholar search]

See also other papers by Erik Demaine.
These pages are generated automagically from a BibTeX file.
Last updated March 9, 2018 by Erik Demaine.