Theoretical and Practical Improvements on the RMQ-Problem, with Applications to LCA and LCE

2006/01/01 by Johannes Fischer, Volker Heun · 84 citations
Computer Science · Engineering · #Algorithms and Data Compression #Computer science #Engineering #Engineering drawing

paper · doi:10.1007/11780441_5

published in Lecture Notes in Computer Science, 36-48 (Springer Berlin Heidelberg)

crossref issued 2006/01/01 · crossref published 2006/01/01 · crossref published-print 2006/01/01 · openalex publication_date 2006/01/01 · crossref created 2006/06/30 · crossref deposited 2021/04/27 · openalex created_date 2025/10/10 · crossref indexed 2026/04/15 · openalex updated_date 2026/07/29

Citations

• Algorithms on Strings, Trees and Sequences
• An Efficient Parallel Biconnectivity Algorithm
• Fast Algorithms for Finding Nearest Common Ancestors
• Replacing suffix trees with enhanced suffix arrays
• The LCA Problem Revisited
• Suffix Arrays: A New Method for On-Line String Searches

Cited by

• Linear-Space Data Structures for Range Mode Query in Arrays
• Algorithms to compute the Burrows-Wheeler Similarity Distribution
• A New Succinct Representation of RMQ-Information and Improvements in the Enhanced Suffix Array
• On Cartesian Trees and Range Minimum Queries
• Cartesian tree [wikipedia]
• Lowest common ancestor [wikipedia]