Recursive Star-Tree Parallel Data Structure

DOI10.1137/0222017zbMATH Open0770.68044OpenAlexW2092901467WikidataQ56563802 ScholiaQ56563802MaRDI QIDQ4032934FDOQ4032934

Authors: Omer Berkman, Uzi Vishkin 

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

Recommendations

• Parallel dynamic lowest common ancestors
• Finding Lowest Common Ancestors in Parallel
• scientific article; zbMATH DE number 753968
• scientific article; zbMATH DE number 54593
• The log-star revolution

zbMATH Keywords

lowest common ancestorsCRCW PRAMrecursive star-tree

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Data structures (68P05) Distributed algorithms (68W15)

Cited In (56)

• Time efficient implementation for online \(k\)-server problem on trees
• Range shortest unique substring queries
• On efficient algorithms for bottleneck path problems with many sources
• A scalable approach to computing representative lowest common ancestor in directed acyclic graphs
• Parallel preprocessing for path queries without concurrent reading.
• One-variable word equations in linear time
• Testing string superprimitivity in parallel
• A work-time optimal algorithm for computing all string covers
• Computing longest common extensions in partial words
• Optimal encodings for range majority queries
• Faster entropy-bounded compressed suffix trees
• Title not available (Why is that?)
• Computing optimal shortcuts for networks
• Dualities in tree representations
• The complexity of parallel prefix problems on small domains
• Pattern matching in a digitized image
• Improved algorithms for the range next value problem and applications
• LRM-trees: compressed indices, adaptive sorting, and compressed permutations
• 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
• Online timestamped text indexing
• Parallel dynamic lowest common ancestors
• A simple linear-space data structure for constant-time range minimum query
• Parallel range minima on coarse grained multicomputers
• The longest common extension problem revisited and applications to approximate string searching
• Array range queries
• Range minimum queries in minimal space
• Encoding two-dimensional range top-\(k\) queries revisited
• Prefix graphs and their applications
• The range 1 query (R1Q) problem
• Finding level-ancestors in trees
• FAST, EFFICIENT MUTUAL AND SELF SIMULATIONS FOR SHARED MEMORY AND RECONFIGURABLE MESH
• Shared memory simulations with triple-logarithmic delay
• Inference algorithms for pattern-based CRFs on sequence data
• Improved algorithms for the multicut and multiflow problems in rooted trees
• Almost fully-parallel parentheses matching
• Spaces, trees, and colors: the algorithmic landscape of document retrieval on sequences
• Extending common intervals searching from permutations to sequences
• Encoding two-dimensional range top-\(k\) queries
• Parallel algorithms for separable permutations
• Heap construction in the parallel comparison tree model
• Constructing suffix arrays in linear time
• Blossom V: A new implementation of a minimum cost perfect matching algorithm
• Internal shortest absent word queries in constant time and linear space
• LS(graph): a constraint-based local search for constraint optimization on trees and paths
• Finding range minima in the middle: approximations and applications
• \textit{MinMax}-profiles: a unifying view of common intervals, nested common intervals and conserved intervals of \(K\) permutations
• Efficient parallel computing with memory faults
• The nearest colored node in a tree
• Simulating shared memory in real time: On the computation power of reconfigurable architectures
• The longest common substring problem
• Improved range minimum queries
• The fast algorithm for online \(k\)-server problem on trees
• On Cartesian trees and range minimum queries
• Entropy-bounded representation of point grids
• Linear time algorithms for generalizations of the longest common substring problem

This page was built for publication: Recursive Star-Tree Parallel Data Structure

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