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)- Efficient algorithms for shortest partial seeds in words
- Efficient seed computation revisited
- A scalable approach to computing representative lowest common ancestor in directed acyclic graphs
- Parallel preprocessing for path queries without concurrent reading.
- Dynamic 3-sided planar range queries with expected doubly-logarithmic time
- scientific article; zbMATH DE number 4047158 (Why is no real title available?)
- Partial and simultaneous transitive orientations via modular decompositions
- Longest substring palindrome after edit
- Longest Lyndon Substring After Edit
- Shortest beer path queries in digraphs with bounded treewidth
- Fast smallest lowest common ancestor computation based on stable match
- Constant query time \((1 + \epsilon)\)-approximate distance oracle for planar graphs
- Distances in benzenoid systems: Further developments
- Swapping a failing edge of a shortest paths tree by minimizing the average stretch factor
- Optimal pointer algorithms for finding nearest common ancestors in dynamic trees
- Computing longest common extensions in partial words
- On Finding Lowest Common Ancestors: Simplification and Parallelization
- Dynamic convex hulls under window-sliding updates
- Geometric hitting set for line-constrained disks
- Approximating geometric bottleneck shortest paths
- Suffix arrays for multiple strings: a method for on-line multiple string searches
- Computing the 4-edge-connected components of a graph: an experimental study
- Recognizing breadth-first search trees in linear time
- Shortest-Path Queries in Geometric Networks
- Efficient algorithms for the minmax regret path center problem with length constraint on trees
- Faster approximate string matching for short patterns
- The use of a pruned modular decomposition for \textsc{maximum matching} algorithms on some graph classes
- Common intervals of trees
- Multidimensional segment trees can do range updates in poly-logarithmic time
- Succinct indices for path minimum, with applications
- When can you fold a map?
- An improved algorithm for the minmax regret path center problem on trees
- Fitting a step function to a point set
- Testing convexity properties of tree colorings
- New common ancestor problems in trees and directed acyclic graphs
- Faster swap edge computation in minimum diameter spanning trees
- Partial and constrained level planarity
- Fast entropy-bounded string dictionary look-up with mismatches
- Fast algorithms for lowest common ancestors on a processor array with reconfigurable buses
- A log log n data structure for three-sided range queries
- Resilient level ancestor, bottleneck, and lowest common ancestor queries in dynamic trees
- Engineering a combinatorial Laplacian solver: lessons learned
- Finding maximal 2-dimensional palindromes
- Some Results for Elementary Operations
- Fast incremental planarity testing
- Finding cores of limited length
- Computing maximal palindromes in non-standard matching models
- Hierarchical categories in colored searching
- Transitions in geometric minimum spanning trees
- Improved space-time tradeoffs for approximate full-text indexing with one edit error
- Rectilinear short path queries among rectangular obstacles
- Fast string matching with k differences
- A uniform approach to semi-dynamic problems on digraphs
- Simpler and Incremental Consistency Checking and Arc Consistency Filtering Algorithms for the Weighted Spanning Tree Constraint
- Cache-oblivious index for approximate string matching
- Building species trees from larger parts of phylogenomic databases
- Approximate shortest paths avoiding a failed vertex: near optimal data structures for undirected unweighted graphs
- Computing on a free tree via complexity-preserving mappings
- A fast and simple Steiner routing heuristic
- A survey on tree edit distance and related problems
- Linear time algorithm for the longest common repeat problem
- Finding lowest common ancestors in arbitrarily directed trees
- Building Cartesian trees from free trees with \(k\) leaves
- Compact and localized distributed data structures
- Efficient retrieval of approximate palindromes in a run-length encoded string
- Improved algorithms for the range next value problem and applications
- Optimal parallel suffix tree construction
- Two flow network simplification algorithms
- Pattern matching in a digitized image
- Approximating points by a piecewise linear function
- On the range maximum-sum segment query problem
- Triply-logarithmic upper and lower bounds for minimum, range minima, and related problems with integer inputs
- An efficient algorithm for some tree matching problems
- Efficient testing and matching of deterministic regular expressions
- A linear-space data structure for range-LCP queries in poly-logarithmic time
- An approximation for finding a smallest 2-edge-connected subgraph containing a specified spanning tree
- Dynamic orthogonal range queries in OLAP.
- Faster Swap Edge Computation in Minimum Diameter Spanning Trees
- NC algorithms for computing a perfect matching and a maximum flow in one-crossing-minor-free graphs
- An efficient strategy for generating all descendant subtree patterns from phylogenetic trees with its implementation
- A faster approximation algorithm for the Steiner tree problem in graphs
- On the restricted 1-Steiner tree problem
- Efficient algorithms for local ranking
- Bicriteria rectilinear shortest paths among rectilinear obstacles in the plane
- Range mode and range median queries in constant time and sub-quadratic space
- Center location problems on tree graphs with subtree-shaped customers
- Tight lower bounds for the longest common extension problem
- Time-Space Trade-Offs for Longest Common Extensions
- Succinct 2D dictionary matching
- A linear-time algorithm for a special case of disjoint set union
- Simplifying and characterizing DAGs and phylogenetic networks via least common ancestor constraints
- On the restricted k-Steiner tree problem
- Online timestamped text indexing
- Longest common extensions in trees
- Order-preserving indexing
- Parameterized complexity dichotomy for \textsc{Steiner Multicut}
- Computing the rooted triplet distance between galled trees by counting triangles
- Reconstructing parameterized strings from parameterized suffix and LCP arrays
- Space-efficient indexes for forbidden extension queries
- Non-overlapping indexing -- cache obliviously
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)
