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

DOI10.1007/11780441_5zbMath1196.68068OpenAlexW2149098716WikidataQ29040132 ScholiaQ29040132MaRDI QIDQ5307491

Publication date: 14 September 2007

Published in: Combinatorial Pattern Matching (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/11780441_5

Mathematics Subject Classification ID

Searching and sorting (68P10) Nonnumerical algorithms (68W05) Data structures (68P05) Computational methods for problems pertaining to biology (92-08)

Related Items (41)

Efficiently computing runs on a trie ⋮ New results on Nyldon words and Nyldon-like sets ⋮ Longest common extensions in trees ⋮ Tight lower bounds for the longest common extension problem ⋮ Time-Space Trade-Offs for Longest Common Extensions ⋮ Computing longest common extensions in partial words ⋮ Fast error-tolerant quartet phylogeny algorithms ⋮ The longest common extension problem revisited and applications to approximate string searching ⋮ Algorithms to compute the Burrows-Wheeler similarity distribution ⋮ Counting distinct palindromes in a word in linear time ⋮ Linear-time superbubble identification algorithm for genome assembly ⋮ Efficient algorithms for three variants of the LPF table ⋮ Finding range minima in the middle: approximations and applications ⋮ The “Runs” Theorem ⋮ Unnamed Item ⋮ Computing runs on a general alphabet ⋮ Period recovery of strings over the Hamming and edit distances ⋮ Unnamed Item ⋮ The longest common substring problem ⋮ Time-space trade-offs for longest common extensions ⋮ An Online Algorithm for Finding the Longest Previous Factors ⋮ Simpler and Incremental Consistency Checking and Arc Consistency Filtering Algorithms for the Weighted Spanning Tree Constraint ⋮ Practical Performance of Space Efficient Data Structures for Longest Common Extensions. ⋮ Shortest rectilinear path queries to rectangles in a rectangular domain ⋮ A simple linear-space data structure for constant-time range minimum query ⋮ Efficient dynamic range minimum query ⋮ Algorithms for finding the weight-constrained \(k\) longest paths in a tree and the length-constrained \(k\) maximum-sum segments of a sequence ⋮ On Cartesian trees and range minimum queries ⋮ A practical semi-external memory method for approximate pattern matching ⋮ On space efficient two dimensional range minimum data structures ⋮ Linear-space data structures for range mode query in arrays ⋮ Analysis of a modification of Gusfield's recursive algorithm for reconstructing ultrametric trees ⋮ Unnamed Item ⋮ Cartesian and Lyndon trees ⋮ Computing runs on a trie ⋮ Faster entropy-bounded compressed suffix trees ⋮ Range minimum queries in minimal space ⋮ LZ-End Parsing in Linear Time ⋮ Almost linear time computation of maximal repetitions in run length encoded strings ⋮ Tree-Based Coarsening and Partitioning of Complex Networks ⋮ Locally Maximal Common Factors as a Tool for Efficient Dynamic String Algorithms.

This page was built for publication: Theoretical and Practical Improvements on the RMQ-Problem, with Applications to LCA and LCE