Nearest common ancestors: a survey and a new algorithm for a distributed environment
From MaRDI portal
Publication:706323
DOI10.1007/s00224-004-1155-5zbMath1093.68136OpenAlexW1980229659WikidataQ29541604 ScholiaQ29541604MaRDI QIDQ706323
Stephen Alstrup, Cyril Gavoille, Theis Rauhe, Haim Kaplan
Publication date: 8 February 2005
Published in: Theory of Computing Systems (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00224-004-1155-5
Related Items
Longest common extensions in trees, Average case analysis for tree labelling schemes, A Simple and Optimal Ancestry Labeling Scheme for Trees, On the range maximum-sum segment query problem, \((r|p)\)-centroid problems on networks with vertex and edge demand, Adjacency Labeling Schemes and Induced-Universal Graphs, Compact separator decompositions in dynamic trees and applications to labeling schemes, Fast Distributed Approximation for TAP and 2-Edge-Connectivity, A scalable approach to computing representative lowest common ancestor in directed acyclic graphs, Finding range minima in the middle: approximations and applications, Ramified rectilinear polygons: coordinatization by dendrons, General compact labeling schemes for dynamic trees, Distance labeling scheme and split decomposition, The saga of minimum spanning trees, Minmax regret 1-sink location problems on dynamic flow path networks with parametric weights, Labeling schemes for weighted dynamic trees, A simple linear-space data structure for constant-time range minimum query, Fast distributed approximation for TAP and 2-edge-connectivity, On space efficient two dimensional range minimum data structures, Faster approximate string matching for short patterns, Randomized proof-labeling schemes, Constructing labeling schemes through universal matrices, Vertex disjoint paths on clique-width bounded graphs, Almost linear time algorithms for minsum \(k\)-sink problems on dynamic flow path networks, A note on models for graph representations, A Fully Dynamic Reachability Algorithm for Directed Graphs with an Almost Linear Update Time, Packed Compact Tries: A Fast and Efficient Data Structure for Online String Processing, Short Labels by Traversal and Jumping, Faster entropy-bounded compressed suffix trees, Shorter Labeling Schemes for Planar Graphs, Inducing Suffix and LCP Arrays in External Memory
