On Cartesian trees and range minimum queries

DOI10.1007/s00453-012-9683-xzbMath1360.68378OpenAlexW2041783148MaRDI QIDQ528853

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

Publication date: 17 May 2017

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-012-9683-x

zbMATH Keywords

partial sumsminimum spanning tree verificationrange minimum querybottleneck pathscache-obliviousCartesian treelowest common ancestor

Mathematics Subject Classification ID

Trees (05C05) Data structures (68P05)

Related Items (12)

Submatrix Maximum Queries in Monge Matrices Are Equivalent to Predecessor Search ⋮ Space efficient data structures for nearest larger neighbor ⋮ The heaviest induced ancestors problem: better data structures and applications ⋮ Unnamed Item ⋮ LZRR: LZ77 parsing with right reference ⋮ Resilient level ancestor, bottleneck, and lowest common ancestor queries in dynamic trees ⋮ Finding patterns and periods in Cartesian tree matching ⋮ Improved Distance Sensitivity Oracles with Subcubic Preprocessing Time. ⋮ Dynamic path queries in linear space ⋮ Compressed range minimum queries ⋮ Cartesian Tree Matching and Indexing ⋮ The Heaviest Induced Ancestors Problem Revisited

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Optimal on-line decremental connectivity in trees
• Linear verification for spanning trees
• Surpassing the information theoretic bound with fusion trees
• A data structure for dynamic trees
• An optimal minimum spanning tree algorithm
• Fast Algorithms for Finding Nearest Common Ancestors
• Two-Dimensional Range Minimum Queries
• Cache-oblivious string dictionaries
• On Cartesian Trees and Range Minimum Queries
• On Finding Lowest Common Ancestors: Simplification and Parallelization
• An On-Line Edge-Deletion Problem
• Recursive Star-Tree Parallel Data Structure
• A randomized linear-time algorithm to find minimum spanning trees
• A minimum spanning tree algorithm with inverse-Ackermann type complexity
• Labeling Schemes for Flow and Connectivity
• Theoretical and Practical Improvements on the RMQ-Problem, with Applications to LCA and LCE
• Cache-oblivious data structures for orthogonal range searching
• An Optimal Cache‐Oblivious Priority Queue and Its Application to Graph Algorithms
• Cache-Oblivious B-Trees
• Lowest common ancestors in trees and directed acyclic graphs

This page was built for publication: On Cartesian trees and range minimum queries