Nearest common ancestors: a survey and a new algorithm for a distributed environment
From MaRDI portal
Publication:706323
DOI10.1007/S00224-004-1155-5zbMATH Open1093.68136OpenAlexW1980229659WikidataQ29541604 ScholiaQ29541604MaRDI QIDQ706323FDOQ706323
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
Recommendations
Cited In (35)
- A scalable approach to computing representative lowest common ancestor in directed acyclic graphs
- Fast distributed approximation for TAP and 2-edge-connectivity
- Short Labels by Traversal and Jumping
- Optimal pointer algorithms for finding nearest common ancestors in dynamic trees
- Near-optimal labeling schemes for nearest common ancestors
- Constructing labeling schemes through universal matrices
- Adjacency labeling schemes and induced-universal graphs
- Faster approximate string matching for short patterns
- General compact labeling schemes for dynamic trees
- Faster entropy-bounded compressed suffix trees
- \((r|p)\)-centroid problems on networks with vertex and edge demand
- 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
- Fast Algorithms for Finding Nearest Common Ancestors
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)
