Nearest common ancestors: a survey and a new algorithm for a distributed environment

DOI10.1007/S00224-004-1155-5MaRDI QIDQ706323zbMATH OpenOpenAlexWikidataFDO

Authors Stephen Alstrup, Cyril Gavoille, Haim Kaplan, Theis Rauhe

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

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05)

Recommendations

• Near-optimal labeling schemes for nearest common ancestors
• Labeling schemes for nearest common ancestors through minor-universal trees
• Fast Algorithms for Finding Nearest Common Ancestors
• scientific article; zbMATH DE number 4047158
• The nearest common ancestor in a dynamic tree

Cited in

(35)

• Fast Algorithms for Finding Nearest Common Ancestors
• A scalable approach to computing representative lowest common ancestor in directed acyclic graphs
• Fast distributed approximation for TAP and 2-edge-connectivity
• Optimal pointer algorithms for finding nearest common ancestors in dynamic trees
• Short Labels by Traversal and Jumping
• Faster approximate string matching for short patterns
• Constructing labeling schemes through universal matrices
• Near-optimal labeling schemes for nearest common ancestors
• Adjacency labeling schemes and induced-universal graphs
• General compact labeling schemes for dynamic trees
• \((r|p)\)-centroid problems on networks with vertex and edge demand
• Faster entropy-bounded compressed suffix trees
• Inducing suffix and LCP arrays in external memory
• Vertex disjoint paths on clique-width bounded graphs
• On the range maximum-sum segment query problem
• Labeling schemes for weighted dynamic trees
• Longest common extensions in trees
• Minmax regret 1-sink location problems on dynamic flow path networks with parametric weights
• Distance labeling scheme and split decomposition
• On space efficient two dimensional range minimum data structures
• A simple and optimal ancestry labeling scheme for trees
• Labeling schemes for nearest common ancestors through minor-universal trees
• The saga of minimum spanning trees
• Average case analysis for tree labelling schemes
• A fully dynamic reachability algorithm for directed graphs with an almost linear update time
• Shorter Labeling Schemes for Planar Graphs
• Ramified rectilinear polygons: coordinatization by dendrons
• A note on models for graph representations
• Almost linear time algorithms for minsum \(k\)-sink problems on dynamic flow path networks
• Compact separator decompositions in dynamic trees and applications to labeling schemes
• Finding range minima in the middle: approximations and applications
• Randomized proof-labeling schemes
• A Data Structure for Nearest Common Ancestors with Linking
• Packed Compact Tries: A Fast and Efficient Data Structure for Online String Processing
• Fast distributed approximation for TAP and 2-edge-connectivity

This page was built for publication: Nearest common ancestors: a survey and a new algorithm for a distributed environment

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