Paper by Erik D. Demaine

Reference:

Erik D. Demaine, Gad Landau, and Oren Weimann, “On Cartesian Trees and Range Minimum Queries”, in Proceedings of the 36th International Colloquium on Automata, Languages and Programming (ICALP 2009), Lecture Notes in Computer Science, volume 5555, Rhodes, Greece, July 5–12, 2009, pages 341–353.

Abstract:

We present new results on Cartesian trees with applications in range minimum queries and bottleneck edge queries. We introduce a cache-oblivious Cartesian tree for solving the range minimum query problem, a Cartesian tree of a tree for the bottleneck edge query problem on trees and undirected graphs, and a proof that no Cartesian tree exists for the two-dimensional version of the range minimum query problem.

Comments:

This paper is also available from SpringerLink.

Length:

The paper is 12 pages.

Availability:

The paper is available in PostScript (355k), gzipped PostScript (167k), and PDF (202k).

See information on file formats.

[Google Scholar search]

Related papers:

Cartesian_Algorithmica (On Cartesian Trees and Range Minimum Queries)