Paper by Erik D. Demaine

Reference:
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.

Abstract:
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)

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

This paper is also available from SpringerLink.

Length:
The paper is 10 pages.

Availability:
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 July 25, 2017 by Erik Demaine.