On Cartesian Trees and Range Minimum Queries

DOI10.1007/978-3-642-02927-1_29zbMath1248.68165OpenAlexW1804493368MaRDI QIDQ3638046

Erik D. Demaine, Gad M. Landau, Oren Weimann

Publication date: 14 July 2009

Published in: Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL: http://hdl.handle.net/1721.1/61963

Mathematics Subject Classification ID

Data structures (68P05) Approximation algorithms (68W25)

Related Items

Succinct indices for path minimum, with applications ⋮ Two dimensional range minimum queries and Fibonacci lattices ⋮ Minimum spanning paths and Hausdorff distance in finite ultrametric spaces ⋮ Unnamed Item ⋮ How rigid the finite ultrametric spaces can be? ⋮ Range Minimum Query Indexes in Higher Dimensions ⋮ Uniqueness of best proximity pairs and rigidity of semimetric spaces ⋮ Bipartite graphs and best proximity pairs ⋮ Encoding 2D range maximum queries ⋮ Cache oblivious algorithms for the RMQ and the RMSQ problems ⋮ Characterizing (quasi-)ultrametric finite spaces in terms of (directed) graphs ⋮ Building Cartesian trees from free trees with \(k\) leaves ⋮ On ultrametric-preserving functions ⋮ Linear-space data structures for range minority query in arrays ⋮ A simple linear-space data structure for constant-time range minimum query ⋮ Combinatorial properties of ultrametrics and generalized ultrametrics ⋮ On Cartesian trees and range minimum queries ⋮ On space efficient two dimensional range minimum data structures ⋮ Linear-space data structures for range mode query in arrays ⋮ Finite ultrametric balls ⋮ The range of ultrametrics, compactness, and separability ⋮ Ultrametric preserving functions and weak similarities of ultrametric spaces ⋮ Orthogonal Range Searching for Text Indexing ⋮ Array Range Queries ⋮ Random Access to Grammar-Compressed Strings and Trees ⋮ Linear-space data structures for range frequency queries on arrays and trees