On Cartesian Trees and Range Minimum Queries

DOI10.1007/978-3-642-02927-1_29MaRDI QIDQ3638046zbMATH OpenOpenAlexFDO

Authors 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)

Recommendations

• On Cartesian trees and range minimum queries
• Succinct representations of binary trees for range minimum queries
• Range median of minima queries, super-Cartesian trees, and text indexing
• On R-trees with low query complexity
• Practical range minimum queries revisited
• Graph searching and a min-max theorem for tree-width
• Optimal succinctness for range minimum queries
• An extremal problem on trees and database theory
• A Compact Index for Cartesian Tree Matching

Cited in

(36)

• On the minimum total length of interval systems expressing all intervals, and range-restricted queries
• Box-trees and R-trees with near-optimal query time
• Combinatorial properties of ultrametrics and generalized ultrametrics
• The range of ultrametrics, compactness, and separability
• Ultrametric preserving functions and weak similarities of ultrametric spaces
• Minimum spanning paths and Hausdorff distance in finite ultrametric spaces
• Linear-space data structures for range mode query in arrays
• Finite ultrametric balls
• Succinct indices for path minimum, with applications
• How rigid the finite ultrametric spaces can be?
• Building Cartesian trees from free trees with \(k\) leaves
• Linear-space data structures for range frequency queries on arrays and trees
• Uniqueness of best proximity pairs and rigidity of semimetric spaces
• Bipartite graphs and best proximity pairs
• Orthogonal range searching for text indexing
• Array range queries
• Two Dimensional Range Minimum Queries and Fibonacci Lattices
• Succinct representations of binary trees for range minimum queries
• Range minimum query indexes in higher dimensions
• Two dimensional range minimum queries and Fibonacci lattices
• Characterizing (quasi-)ultrametric finite spaces in terms of (directed) graphs
• Linear-space data structures for range minority query in arrays
• scientific article; zbMATH DE number 7255037 (Why is no real title available?)
• On ultrametric-preserving functions
• Random access to grammar-compressed strings and trees
• On Cartesian trees and range minimum queries
• Box-trees and R-trees with near-optimal query time
• Amortized Rigidness in Dynamic Cartesian Trees
• Cache oblivious algorithms for the RMQ and the RMSQ problems
• Algorithms and hardness for the longest common subsequence of three strings and related problems
• Encodings for range minimum queries over bounded alphabets
• Space complexity of vertex connectivity oracles
• On space efficient two dimensional range minimum data structures
• Faster path queries in colored trees via sparse matrix multiplication and min-plus product
• Encodings for range minimum queries over bounded alphabets
• Steinhaus filtration and stable paths in the mapper

This page was built for publication: On Cartesian Trees and Range Minimum Queries

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3638046)