Recursive Star-Tree Parallel Data Structure
From MaRDI portal
Publication:4032934
DOI10.1137/0222017zbMath0770.68044OpenAlexW2092901467WikidataQ56563802 ScholiaQ56563802MaRDI QIDQ4032934
Publication date: 17 May 1993
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0222017
Analysis of algorithms and problem complexity (68Q25) Data structures (68P05) Distributed algorithms (68W15)
Related Items
Optimal encodings for range majority queries ⋮ Finding level-ancestors in trees ⋮ Pattern matching in a digitized image ⋮ Online timestamped text indexing ⋮ Almost fully-parallel parentheses matching ⋮ Parallel dynamic lowest common ancestors ⋮ Efficient parallel computing with memory faults ⋮ Heap construction in the parallel comparison tree model ⋮ Computing longest common extensions in partial words ⋮ Inference algorithms for pattern-based CRFs on sequence data ⋮ FAST, EFFICIENT MUTUAL AND SELF SIMULATIONS FOR SHARED MEMORY AND RECONFIGURABLE MESH ⋮ Improved range minimum queries ⋮ Simulating shared memory in real time: On the computation power of reconfigurable architectures ⋮ The range 1 query (R1Q) problem ⋮ The complexity of parallel prefix problems on small domains ⋮ Encoding two-dimensional range top-\(k\) queries ⋮ Entropy-bounded representation of point grids ⋮ A scalable approach to computing representative lowest common ancestor in directed acyclic graphs ⋮ Internal shortest absent word queries in constant time and linear space ⋮ The longest common extension problem revisited and applications to approximate string searching ⋮ Shared memory simulations with triple-logarithmic delay ⋮ Finding range minima in the middle: approximations and applications ⋮ The nearest colored node in a tree ⋮ Prefix graphs and their applications ⋮ Improved algorithms for the range next value problem and applications ⋮ The longest common substring problem ⋮ Extending common intervals searching from permutations to sequences ⋮ LS(graph): a constraint-based local search for constraint optimization on trees and paths ⋮ A work-time optimal algorithm for computing all string covers ⋮ A simple linear-space data structure for constant-time range minimum query ⋮ \textit{MinMax}-profiles: a unifying view of common intervals, nested common intervals and conserved intervals of \(K\) permutations ⋮ On Cartesian trees and range minimum queries ⋮ LRM-trees: compressed indices, adaptive sorting, and compressed permutations ⋮ Computing optimal shortcuts for networks ⋮ Parallel algorithms for separable permutations ⋮ Linear time algorithms for generalizations of the longest common substring problem ⋮ Spaces, Trees, and Colors ⋮ Analysis of a modification of Gusfield's recursive algorithm for reconstructing ultrametric trees ⋮ Range mode and range median queries in constant time and sub-quadratic space ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Blossom V: A new implementation of a minimum cost perfect matching algorithm ⋮ Improved algorithms for the multicut and multiflow problems in rooted trees ⋮ Unnamed Item ⋮ Faster entropy-bounded compressed suffix trees ⋮ Range minimum queries in minimal space ⋮ Array Range Queries ⋮ Constructing suffix arrays in linear time ⋮ PARALLEL RANGE MINIMA ON COARSE GRAINED MULTICOMPUTERS ⋮ The fast algorithm for online \(k\)-server problem on trees ⋮ Parallel preprocessing for path queries without concurrent reading. ⋮ Testing string superprimitivity in parallel ⋮ One-variable word equations in linear time
