Fast Algorithms for Finding Nearest Common Ancestors
From MaRDI portal
Recommendations
- Faster algorithms for finding lowest common ancestors in directed acyclic graphs
- Near-optimal labeling schemes for nearest common ancestors
- scientific article; zbMATH DE number 4064469
- On Finding Lowest Common Ancestors: Simplification and Parallelization
- Fast Lowest Common Ancestor Computations in Dags
- A Data Structure for Nearest Common Ancestors with Linking
- Nearest common ancestors: a survey and a new algorithm for a distributed environment
- Fast smallest lowest common ancestor computation based on stable match
- Optimal pointer algorithms for finding nearest common ancestors in dynamic trees
- Optimal Pointer Algorithms for Finding Nearest Common Ancestors in Dynamic Trees
Cited in
(only showing first 100 items - show all)- Center location problems on tree graphs with subtree-shaped customers
- Efficient algorithms for two generalized 2-median problems and the group median problem on trees
- The Level-Ancestor problem on pure pointer machines
- Improved algorithms for the multicut and multiflow problems in rooted trees
- Real two dimensional scaled matching
- Matching subsequences in trees
- Data compression for proof replay
- Two flow network simplification algorithms
- A linear-time algorithm for a special case of disjoint set union
- Parallel string matching with k mismatches
- Computing on a free tree via complexity-preserving mappings
- An \(O(ND)\) difference algorithm and its variations
- Data structures and algorithms for approximate string matching
- A log log n data structure for three-sided range queries
- Fast string matching with k differences
- The suffix tree of a tree and minimizing sequential transducers
- An efficient algorithm for some tree matching problems
- Fast algorithms for lowest common ancestors on a processor array with reconfigurable buses
- Transitions in geometric minimum spanning trees
- Stacks, queues, and deques with order-statistic operations
- Two-dimensional dictionary matching
- Randomized range-maxima in nearly-constant parallel time
- A uniform approach to semi-dynamic problems on digraphs
- A fast and simple Steiner routing heuristic
- New algorithms for the LCA problem and the binary tree reconstruction problem
- Finding level-ancestors in trees
- Finding lowest common ancestors in arbitrarily directed trees
- Ray shooting in polygons using geodesic triangulations
- Unit-cost pointers versus logarithmic-cost addresses
- Pattern matching in a digitized image
- A constant update time finger search tree
- Almost fully-parallel parentheses matching
- Rectilinear short path queries among rectangular obstacles
- A note on finding compact sets in graphs represented by an adjacency list
- A simpler minimum spanning tree verification algorithm
- Tree structure for distributive lattices and its applications
- Dynamic orthogonal range queries in OLAP.
- The complexity of the locally connected spanning tree problem
- Tight bounds on the solutions of multidimensional divide-and-conquer maximin recurrences
- Distances in benzenoid systems: Further developments
- Space-efficient indexes for forbidden extension queries
- Computing longest common extensions in partial words
- The nearest colored node in a tree
- Motif trie: an efficient text index for pattern discovery with don't cares
- Efficient algorithms for shortest partial seeds in words
- Constant query time \((1 + \epsilon)\)-approximate distance oracle for planar graphs
- Engineering a combinatorial Laplacian solver: lessons learned
- Finding maximal 2-dimensional palindromes
- A \(\min\)-\(\max\) relation in flowgraphs and some applications
- Dynamic relative compression, dynamic partial sums, and substring concatenation
- A new framework for addressing temporal range queries and some preliminary results
- A faster approximation algorithm for the Steiner tree problem in graphs
- The nearest common ancestor in a dynamic tree
- A data structure for dynamic trees
- Parallel preprocessing for path queries without concurrent reading.
- An approximation for finding a smallest 2-edge-connected subgraph containing a specified spanning tree
- An optimal data structure to handle dynamic environments in non-deterministic computations
- When can you fold a map?
- Approximating geometric bottleneck shortest paths
- A robust model for finding optimal evolutionary tree
- Linear time algorithms for two disjoint paths problems on directed acyclic graphs
- An introduction to the Ribe program
- Drawing trees with perfect angular resolution and polynomial area
- Approximate shortest paths avoiding a failed vertex: near optimal data structures for undirected unweighted graphs
- Constructing the R* consensus tree of two trees in subcubic time
- A few logs suffice to build (almost) all trees. II
- The lowest common ancestor problem on a tree with an unfixed root
- An improved algorithm for tree edit distance with applications for RNA secondary structure comparison
- On the restricted 1-Steiner tree problem
- Internal dictionary matching
- Multiple-edge-fault-tolerant approximate shortest-path trees
- Range minimum queries in minimal space
- On the restricted k-Steiner tree problem
- Optimal centrality computations within bounded clique-width graphs
- The fast algorithm for online \(k\)-server problem on trees
- Efficient algorithms for the minmax regret path center problem with length constraint on trees
- The heaviest induced ancestors problem: better data structures and applications
- Computing \(k\)-centers of uncertain points on a real line
- Finding all minimum cost flows and a faster algorithm for the \(K\) best flow problem
- An improved algorithm for the minmax regret path center problem on trees
- Dynamic planar range skyline queries in log logarithmic expected time
- 2-dimensional palindromes with k mismatches
- Multidimensional segment trees can do range updates in poly-logarithmic time
- Computing longest palindromic substring after single-character or block-wise edits
- Efficient counting of square substrings in a tree
- Reporting and counting maximal points in a query orthogonal rectangle
- \(L_{1}\) shortest path queries in simple polygons
- Fast parallel and serial multidimensional approximate array matching
- Indexing weighted sequences: neat and efficient
- A polynomial matrix processing heuristic algorithm for finding high quality feasible solutions for the TSP
- Quickest visibility queries in polygonal domains
- Analytical description of digital intersections: minimal parameters and multiscale representation
- Bicriteria rectilinear shortest paths among rectilinear obstacles in the plane
- Approximate periodicity
- Geometric biplane graphs. II: Graph augmentation
- Computing the \(K\)-terminal reliability of directed path graphs
- Disconnectivity and relative positions in simultaneous embeddings
- Succinct indices for path minimum, with applications
- Optimal parallel verification of minimum spanning trees in logarithmic time
- Faster algorithms for finding lowest common ancestors in directed acyclic graphs
This page was built for publication: Fast Algorithms for Finding Nearest Common Ancestors
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3319776)
