zbMATH — the first resource for mathematics

On Cartesian trees and range minimum queries. (English) Zbl 1248.68165
Albers, Susanne (ed.) et al., Automata, languages and programming. 36th international colloquium, ICALP 2009, Rhodes, Greece, July 5–12, 2009. Proceedings, Part I. Berlin: Springer (ISBN 978-3-642-02926-4/pbk). Lecture Notes in Computer Science 5555, 341-353 (2009).
Summary: 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.
For the entire collection see [Zbl 1166.68001].

68P05 Data structures
68W25 Approximation algorithms
Full Text: DOI