Paper by Erik D. Demaine
- 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.
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.
- This paper is also available from SpringerLink.
- The paper is 12 pages.
- 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)
See also other papers by Erik Demaine.
These pages are generated automagically from a
Last updated July 21, 2021 by